[Algorithm] DFS로 순열 구하기(C++)

순열이란 서로 다른 n개 중 r개를 뽑는 경우의 수를 의미한다. 이를 구현하는 방법은 다양하지만 오늘은 DFS로 순열의 각 경우를 구해보고, 그 전체 경우의 수를 함께 알아낼 것이다.

그림으로 이번 포스팅에서 다룰 순열 구하기가 어떤 과정을 거치는지 살펴보자.

{1, 3, 6, 7}이라는 수열이 있을 때, 그 순열은 위와 같은 순서로 얻어진다.

트리 구조로 표현하였으며, 전위(preorder) 즉, 접근한 노드의 왼쪽 자식부터 오른쪽 자식 순서로 과정이 그려진다고 가정하고, 수열의 좌측부터 우측 순서대로 인덱스에 접근한다. 위 그림이 뜻하는 바를 설명하자면

• perm(cnt) : 이전의 과정을 거치며 순열에 cnt개의 요소가 담겨 있음을 의미.
• 초록색 요소 : 현재 단계에서 접근 중인 요소.
• / : 이전의 과정을 거치며 이미 해당 요소는 사용 중임을 의미.

첫 번째 요소부터 시작하여 초반 4개의 숫자 조합은 위와 같은 순서로 얻어진다. 이후도 같은 방식으로 이루어진다. dfs를 이용하고, perm(cnt)라고 표현한 것에서 예상할 수 있는 것처럼 재귀 형태의 알고리즘을 가진다.

바로 코드를 살펴보자.

#include <iostream>
#define MAX_SIZE 20

int n, r;
int arr[MAX_SIZE], visit[MAX_SIZE], print[MAX_SIZE];

void perm_dfs(int count) {
	if (count == r) {
		for (int tmp = 0; tmp < r; tmp++) {
			printf("%d ", print[tmp]);
		}
		printf("\n");
	}
	else {
		for (int index = 0; index < n; index++) {
			if (!visit[index]) {
				print[count] = arr[index];
				visit[index] = 1;
				perm_dfs(count + 1);
				visit[index] = 0;
			}
		}
	}
}

int main() {
	for (int index = 0; index < MAX_SIZE; index++) {
		arr[index] = 0;
		visit[index] = 0;
		print[index] = 0;
	}

	scanf("%d %d", &n, &r);
	for (int index = 0; index < n; index++) {
		scanf("%d", &arr[index]);
	}

	perm_dfs(0);
}

---

▼ 예시 입력 n = 4, r = 3, 수열 = {1, 3, 6, 7}에 대한 출력 결과

앞선 그림을 통한 예제를 이해하였다면 읽기 어려운 코드는 아닐 것이니 코드에 대한 자세한 설명은 생략하겠다. 그림으로도 잘 이해하지 못 하였다면 해당 코드를 IDE에서 한 줄씩 디버깅을 돌려도 충분히 이해할 수 있을 것이다.