백트래킹 - 15649 N과 M (1)

백트래킹 : 현재 가능한 상태에서 모든 후보군을 따라 들어가며 탐색하는 알고리즘.

 

코드

#include <stdio.h>

void fn(int x);

int n, m;
int arr[8] = {};
int isused[9] = {}; /* 1~8의 숫자가 들어갈 거라서, isused[8]로 만들어버리면
                       isused[0]~isused[7]이 만들어지기 때문에 isused[i]=1을 설정할 때
                       i가 8이면 값이 들어가지 못함.*/

int main() {
	scanf_s("%d %d", &n, &m);
	fn(0);
}

void fn(int x) {
	if (x == m) {
		for (int i = 0; i < m; i++) {
			printf("%d", arr[i]);
			if (i != m - 1)
				printf(" ");
		}
		printf("\n");
		return;
	}

	for (int i = 1; i <= n; i++) { // 1~n까지의 수에 대해. (i=0~i<n이면 0~n-1까지의 수를 넣는것)
		if (!isused[i]) {
			arr[x] = i;
			isused[i] = 1;

			fn(x + 1);
			isused[i] = 0;
		}
	}
}

 

실수가 있었던 부분에 주석을 달아놨다.

 

참고한 블로그

[Python] 백트래킹 (+ DFS와 차이)

 

[실전 알고리즘] 0x0C강 - 백트래킹