💡 백트래킹
Memory 2020KB Time 0ms Code Length 530B
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
#include<iostream>
#include<vector>
using namespace std;
int N, M; // 최대숫자, 갯수
int visited[9];
void init() {
cin >> N >> M;
}
int cnt = 0;
vector<int> vc;
void dfs(int depth, int idx) {
if (depth == M) {
for (auto i : vc) {
cout << i << " ";
}
cout << '\n';
return;
}
for (int i = idx; i <= N; i++) {
if (visited[i] == 1) continue;
visited[i] = 1;
vc.push_back(i);
dfs(depth + 1, i+ 1);
vc.pop_back();
visited[i] = 0;
}
}
int main()
{
ios::sync_with_stdio(false);
init();
dfs(0,1);
}
이 코드는 주어진 숫자 범위 내에서 중복 없이 M개의 숫자를 선택하는 모든 경우의 수를 출력하는 프로그램이다.
- init 함수에서는 N과 M을 입력받는다.
- dfs 함수는 깊이(depth)와 시작 인덱스(idx)를 인자로 받아 재귀적으로 숫자를 선택하고 출력한다.
- 재귀 호출을 통해 모든 경우의 수를 탐색하며, 선택한 숫자는 visited 배열을 통해 중복 선택을 방지한다.
- 선택한 숫자는 vc 벡터에 추가되고, 재귀 호출 후에는 다시 제거된다.
- 모든 경우의 수를 탐색한 후에는 결과를 출력한다.
즉, 이 코드는 백트래킹을 이용하여 숫자를 선택하고 출력하는 과정을 반복하여 모든 경우의 수를 출력하는 프로그램이다.
