💡 백트래킹
Memory 2020KB Time 28ms Code Length 511B
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) {
if (depth == M) {
for (auto i : vc) {
cout << i << " ";
}
cout << '\n';
return;
}
for (int i = 1; i <= N; i++) {
if (visited[i] == 1) continue;
visited[i] = 1;
vc.push_back(i);
dfs(depth + 1);
vc.pop_back();
visited[i] = 0;
}
}
int main()
{
ios::sync_with_stdio(false);
init();
dfs(0);
}
- init 함수를 통해 N과 M 값을 입력받는다.
- dfs 함수는 재귀적으로 숫자를 선택하고 출력하는 함수이다.
- depth가 M과 같아지면 선택한 숫자들을 출력하고 함수를 종료한다.
- 1부터 N까지의 숫자를 선택하며, 이미 선택된 숫자인 경우에는 건너뛴다.
- 선택한 숫자를 visited 배열에 표시하고 vc 벡터에 추가한 뒤, 다음 depth로 이동한다.
- 이후 선택한 숫자를 다시 제거하고 visited 배열을 초기화하여 다른 경우의 수를 탐색한다.
- main 함수에서는 초기화를 한 뒤에 dfs 함수를 호출하여 실행한다.
