백준 [15649] "N과 M"

15649

DFS를 Backtracking 기법을 이용해서 해결하는 문제이다.

1. DFS를 이용할 재귀 함수를 만들고 k를 통해 깊이를 입력받는다. 현재 깊이를 입력값 m과 비교해 맞다면 결과를 출력하고 아니라면 아래 반복문을 시행한다.

void backtracking(int k) {
	if (k == m) 
	{
		for (int i = 0; i < m; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
    for (int i = 1; i <= n; i++) 
	{
		if (!visited[i]) {
			visited[i] = true;
			arr[k] = i;
			backtracking(k + 1);
			visited[i] = false;
		}
	}
}

2. 방문했는지를 검사해 만약 기록이 없다면 arr[k] = i를 선언하고 재귀 함수를 실행한다.

    for (int i = 1; i <= n; i++) 
	{
		if (!visited[i]) {
			visited[i] = true;
			arr[k] = i;
			backtracking(k + 1);
			visited[i] = false;
		}
	}

여기서 이 문제를 이해하는데 시간이 상당히 오래 걸렸는데 만약 입력이 3,1 이 들어온 상황이라면 backtracking(k+1)이 3번 실행 될 것이고 위 (1) 과정이 3번 반복되면서 결과가
1 2 3 이 아닌 1 1 2 1 2 3이 나오는게 맞는게 아닌가 라는 의문점이 들었다.
그 이유는 arr[k]에서 k는 위에서 재귀함수의 매개변수로 받기에 재귀 내에서는 바뀔 일이 없는데 이를 i와 혼동해 생긴 문제였다. 결국 3번의 반복은 모두 arr[1] = 1, arr[1] = 2, arr[3] = 3이기에 정상 적으로 1 2 3이 출력된다.

#include <iostream>
#include <deque>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <queue>

#define MAX 9

using namespace std;

int arr[MAX] = { 0, };
bool visited[MAX] = { 0, };
int n, m;

void backtracking(int k) {
	if (k == m) 
	{
		for (int i = 0; i < m; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) 
	{
		if (!visited[i]) {
			visited[i] = true;
			arr[k] = i;
			backtracking(k + 1);
			visited[i] = false;
		}
	}
}

int main(void) {
	
	cin >> n >>m;

	backtracking(0);

	return 0;
}