DFS를 사용한 순열 구하기

참고 문서

• 이 블로그의 문서: Swap을 사용한 순열 구하기
• GitHub: 이 프로젝트의 리포지토리(algorithm)

이 문서의 내용

순열이란 n개의 값 중에서 r개의 값을 뽑는 모든 경우의 수를 의미합니다.

예를 들어 1, 2, 3 값 중에서 2개의 값을 뽑는 모든 경우의 수는 다음과 같습니다. 순열은 값의 중복을 배제하지 않기 때문에 1, 2 그리고 2, 1이 동시에 나타납니다.

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

DFS란?

깊이 우선 탐색(DFS, Depth-First Search)은 그래프의 시작 노드를 기준으로 탐색 할 수 있는 가장 깊은 노드까지 진행합니다.

탐색은 마지막 노드에 도달했을 때 종료되고 이전 노드로 돌아온다음 분기된 다른 노드를 이어서 탐색합니다.

예시의 그래프에서 DFS를 실행하면 0, 1, 2 0, 1, 3 0, 4, 5, 6 0, 4, 5, 7의 탐색 경로를 구할 수 있습니다.

public class DFS
{
	protected static void dfs(int[] arr, boolean[] visited, int depth, int r)
	{
		if (depth == r)
			return;
		
		for (int i = 0; i < arr.length; ++i)
		{
			if (visited[i])
				continue;
			visited[i] = true;
			dfs(arr, visited, depth + 1, r);
			// 원위치
			visited[i] = false;
		}
}

코드		비고
Line 3	boolean[] visited	현재 탐색 경로가 어떤 노드를 방문했는지 마킹합니다.
Line 8:16	for (i = 0; i < arr.length; ++i) { }	현재 노드를 탐색하고 다음 노드로 DFS합니다. 다음 노드 탐색이 완료되면 현재 노드의 마킹을 취소합니다.

DFS를 사용한 순열 흐름도

DFS를 진행하면서 순열을 계산합니다.

깊이(depth)는 0부터 시작해서 뽑으려는 수 r에 도달하면 탐색을 마치고 이전 depth로 돌아갑니다.

예시의 흐름도에서 depth = 3의  1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 6개의 경우의 수가 발생합니다. 

이 블로그의 문서: Swap을 사용한 순열 구하기와 달리 DFS를 사용하면 순열의 순서가 보장됩니다.

예를 들어 흐름도의 마지막 2개 순열은 기대값 3, 1, 2 그리고 3, 2, 1과 일치합니다.

DFS를 사용한 순열 구현

순열을 계산하기 위한 인자는 arr depth r 그리고 순열의 결과를 저장하는 out과 탐색 경로를 마킹하는 visited입니다.

depth의 초기 값은 0으로 시작합니다. r은 주어진 배열에서 몇 개의 수를 뽑아낼 것인가를 의미합니다.

public class DFS
{
	protected static void permutation(int[] arr, int[] out, boolean[] visited, int depth, int r)
	{
		if (depth == r)
		{
			printResult(out, r);
			return;
		}

		for (int i = 0; i < arr.length; ++i)
		{
			if (visited[i])
				continue;
			visited[i] = true;
			out[depth] = arr[i];
			permutation(arr, out, visited, depth + 1, r);
			// 원위치
			out[depth] = 0;
			visited[i] = false;
		}
	}
}

코드		비고
Line 5:9	if (depth == r)	depth가 r에 도달하면 하나의 경우의 수가 발생합니다.
Line 11	for (i = 0; i < arr.length; ++i)	현재 depth에서 방문하지 않은 노드를 모두 방문합니다.
Line 15:17	visited[i] = true	현재 인덱스의 노드를 방문합니다.
	out[depth] = arr[i]	현재 인덱스의 노드를 순열에 저장합니다.
	permutation()	다음 depth를 진행하기 위해 재귀호출합니다.
Line 18:20	out[depth] = 0 visited[i] = false	새로운 순열을 찾기 위해 현재 인덱스의 노드를 원위치합니다.