[백준] 15650번 N과 M (2) - c++

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

#include<iostream>

using namespace std;
int arr[9];
bool visited[9] = {false,};
int n, m;
void dfs(int num , int cnt ) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
	}
	else {
		for (int i = num; i <=n ; i++) {
			if (!visited[i]) {
				visited[i] = true;
				arr[cnt] = i;
				dfs(i + 1, cnt + 1);
				visited[i] = false;
			}
		}
	}
}
int main() {
	
	cin >> n >> m;
	dfs(1,0);
}

재귀와 백트래킹은 너무 어렵다. ㅠㅠ

우선 이문제를 풀기 위해서는 문제의 이해가 필요하다. 

else {
		for (int i = num; i <=n ; i++) {
			if (!visited[i]) {
				visited[i] = true;
				arr[cnt] = i;
				dfs(i + 1, cnt + 1);
				visited[i] = false;
			}
		}
	}

특히 이 부분이 필수이다.

배열에 방문을 하지 않은 경우 방문처리를 해주고 

그배열에 i 수를 넣어준다 (arr 배열을 나중에 출력을 해준다)

여기서 재귀로다시 dfs 를 실행해준다. 

이때 dfs를 실행해주면서 두가지 인수를 1씩 증가해준다. (num, cnt)

왜 증가해주냐면? 두인수에 맞게 함수를 실행해야하는데 

여기서 cnt는 수열의 길이를 의미한다. cnt가 증가하는 것을 체크해주어야

함수를 중단해줄수 있기 때문이다.

num은 여기서 진행되는 값을 나타낸다. 우리는 n까지 반복문을 진행해주면서 이 함수를 진행해야한다.

num을 1씩 증가해주면서 중복이 생기지 않게 해주기 위함이다. (이문제는 조합을 나타내기 때문이다.)

함수를 마치게 된다면 우린는 그 방문한 visited[i] 의 방문을 다시 false로 해주는데 그이유는 

우리는 그 함수가 더이상 이제 깊이 못들어간다는 것을 의미하게 되기 때문에 비 방문으로 초기화 해주기 때문이다.

근데 여기서 의문이 생길수 있다

뭐냐하면 왜 arr의 값은 초기화 안해줌?

이럴수 있는데 초기화를 안해주고 우리는 그냥 새로운 값을 대입하기 때문이다.