문제
풀이
전형적인 백트래킹 문제라고 한다. 주어진 범위가 주어지면 순열과 조합을 찾는 문제로서, 재귀함수 호출을 이용한 풀이로 진행하였다.
Iteration과 재귀함수 호출을 이용해 문제를 해결하는 부분이다. N과 M이 각각 4, 2라면 맨 처음 array에 [1]이 담겨있다가, function call로 인해 [1, 2]가 담기고,
그 이후 function call로 인해 그 arr가 print 된다. 그 후 return으로 인해 result.pop_back() 으로 인해 arr가 [1]이 되고 난 뒤, iteration이 진행되어 [1, 3]이 담기고
그 이후 function call로 인해 print가 되는 것을 반복하는 방식이다. 또 check array를 통해서 중복이 되는 것을 방지하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void DFS(int cnt){
if(cnt == M){
for(int i = 0; i<M; i++){
printf("%d ", result[i]);
}
cout << "\n";
return;
}
for(int i = 0;i<N;i++){
if(check[i] == true) continue;
else{
check[i] = true;
result.push_back(arr[i]);
DFS(cnt+1);
result.pop_back();
check[i] = false;
}
}
소스 코드
조합문제이면서, 중복을 허용하지 않는 N과M(2) 문제의 소스코드이다. 1, 3, 4번 문제도 중복을 하냐, 시작점을 처음부터하는가 그 앞자리 수보다 큰 숫자로 하는가의 부분의 차이로 순열과 조합 문제 풀이가 가능하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<int> result;
int arr[8];
bool check[8];
bool start[8];
void combination(int start, int cont){
if(cont == M){
for(int i = 0; i<M; i++){
printf("%d ", result[i]);
}
cout << "\n" ;
return;
}
for(int i = start; i<N; i++){
if(check[i] == true) continue;
else{
check[i] = true; // 중복을 피해주기 위함
result.push_back(arr[i]);
combination(i+1, cont+1); // 시작점을 키워서 조합 문제 풀이로 변경.
result.pop_back();
check[i] = false;
}
}
}
int main(){
scanf("%d %d", &N, &M);
for(int i = 0; i<N; i++){
arr[i] = i+1;
}
combination(0, 0);
}
