백준 / 백트래킹 / 15649번 / N과 M (1) / C++

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며,
각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 

3 1

예제 출력 1 

1
2
3

예제 입력 2 

4 2

예제 출력 2 

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

 

 

#include <iostream>
using namespace std;

const int MAX = 8 + 1;
int arr[MAX];
bool visited[MAX] = {false, };
int n, m;

void f(int cnt) {
	if(cnt == m) {
		for(int i=0; i<m; i++) {
			cout << arr[i] << " ";
		}
		cout << '\n';
	}
	else {
		for(int i=1; i<=n; i++) {
			if(!visited[i]) {
				visited[i] = true;
				arr[cnt] = i;
				f(cnt + 1);
				visited[i] = false;
			}
		}
	}	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	f(0);		

	return 0;
}

---

일단 m개로 만들 수 있는 조합을 저장하는 배열 arr와 방문했는지 안했는지를 판별해주는 visited 배열을 만들어준다.

visited는 false로 초기화해준다.

 

예를 n=4, m=2로 하고 단계별로 설명해보겠다.

조합은 1부터의 조합이기 때문에 1부터 n까지 반복문을 돌려준다.

 

1. f(0)
   만약 visited[1]이 false라면, 즉 visited[1]을 방문하지 않았다면 visited[1]을 true로 바꾸고,
   arr[0]을 i(1)로 바꿔준다.
   여기서 0은 함수의 매개변수로 들어오는 cnt의 초기값이다.
   
   현재값은
   arr[9] = {1, 0, ... , 0}
   visited[9] = {false, true, false, ... , false}
   위와 같이 된다.
   
   cnt가 m과 같아질때까지 재귀를 돌린다.
   따라서 f(1)로 가게된다.
   
   
2. f(1)
   아직 cnt가 m이 안됬으므로 else의 반복문으로 들어가게 된다.
   그런데 visited[1]이 f(0)에서 true가 되었으므로(방문했으므로) visited[2]를 방문하게 된다.
   visited[2]를 true로 바꿔주고 arr[1] = 2가 된다. 
   
   현재값은
   arr[9] = {1, 2, ... , 0}
   visited[9] = {false, true, true, false, ... , false}
   위와 같이 된다.
   
   그리고 f(2)로 넘어가게 된다.
3. f(2)
   cnt와 m이 같아졌으므로 arr에 있는 1과 2를 출력해준다.
   그 후 f(2)가 끝났으므로 f(1)로 돌아가게 된다.
4. f(1)
   f(cnt+1)이 끝났으므로 그 다음줄인 visited[i] = false를 실행하게 된다.
   f(2)로 넘어가기 전의 f(1)에서 i가 2였으므로 visited[2] = false가 된다.
   
   현재값은
   arr[9] = {1, 2, ... , 0}
   visited[9] = {false, true, false, false, ... , false}
   위와 같이 된다.
   
   그러면 f(1)의 i=2일때의 반복문이 모두 끝났으므로 i=3이 된다.
   따라서 위와 같이 visited[3] = true가 되고, arr[1] = 3이 된다.
   
   현재값은
   arr[9] = {1, 3, ... , 0}
   visited[9] = {false, true, false, true, false, ... , false}
   위와 같이 된다.
   
   그리고 f(cnt + 1)에 의해 f(2)로 넘어가게 된다.
5. f(2)
   cnt와 m이 같아졌으므로 arr에 있는 1과 3을 출력해준다.
   그리고 다시 f(1)로 돌아간다.

=> 이후 과정은 위가 반복되면서 같다.

 

백트래킹 기법을 구글링해서 보고 이해하려 했지만 쉽지 않았다.

결국 나중에 문제를 다시보고 이해를 해봤는데, 재귀를 이해하는데는 그림을 그리면서 하는것이 가장 빠른것같다.

 

만약 위 과정이 이해가 잘 가지 않는다면 f(0)부터 arr와 visited가 어떻게 변화되는지 그려보면 이해가 잘 될 것이다.