15649 : N과 M (1)

네르기·2021년 8월 27일

DFS 백트래킹 생각

알고리즘

목록 보기

29/76

어떤 문제인가?

백트래킹을 쓰는 문제.

이게 도대체 뭔...

처음 문제를 풀 때, 뭔지 모르겠는 부분이 있었다.

백트래킹 예제들을 보니까 DFS를 쓰고, 이 DFS는 트리 또는 그래프 탐색에 근간한 개념이다. 근데 예제에서는 그래프랑 트리를 직접 쓴다는 가정하에 설명된 게 많은데, 문제에서 제시하는 건 배열 뿐이다. 어떻게 하란건가?
설령 배열을 트리 혹은 그래프로 온전히 옮겼다 하더라도, 수열에 있는 값들은 여러 번 나오는데, 이들을 구분할 유일한 값은 어떻게 부여해야 하는가?

DFS 개념도 보고, 백트래킹도 보고 했지만 도저히 감을 못 잡았다. 그래서 답을 봤다. 하루종일 잡아도 못풀 것 같다는 생각이 들었다.

음... 그런 개념이

우선 내 코드는 아니다. 남들의 코드를 먼저 인용하겠다.

#include <stdio.h>

int r[8], n, m, v[9];

void recur(int k) {
	int i;
	if (k == m) {
		for (i = 0 ; i < m ; i++) printf("%d ", r[i]);
		printf("\n");
		return;
	}
	for (i = 1 ; i <= n ; i++) {
		if (!v[i]) {
			v[i] = 1, r[k] = i;
			recur(k + 1);
			v[i] = 0;
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	recur(0);
}