목차
1. 백트래킹 알고리즘이란?
- 모든 경우에 수에 대해 탐색
- 탐색 중에 해당 경로가 해가 될 가능성이 없다면 경로를 되돌아가 다시 결과를 찾는다. (가지치기)
- 주로 DFS(깊이 우선 탐색) 방식으로 확인한다.
2. 로직
가. 유망성 검사
- 해가 될 가능성이 있는지 조건을 설정한다.
나. 가지치기
- 유망성 검사를 통해 가능성이 없는 경로를 차단(가지치기) 하여 탐색의 효율성을 높인다.
3. 구현
문제 예시
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
|
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
42
43
|
#include <iostream>
#include <vector>
using namespace std;
int N, M; // 탐색 범위, 탐색 깊이
vector<int> v; // 탐색한 수열 저장
bool visited[9] = { 0, }; // 방문여부
void backtracking(int idx)
{
if (idx == M) // 탐색한 수열 출력
{
for (int i = 0; i < M; ++i)
{
cout << v[i] << ' ';
}
cout << '\n';
}
for (int i = 1; i <= N; ++i)
{
if (!visited[i]) // 방문한 적이 없는 경로로만 탐색 (방문했던 곳 가지치기)
{
visited[i] = true;
v.push_back(i); // 탐색 경로 저장
backtracking(idx + 1); // 재귀를 이용해 해당 경로의 깊은 곳을 탐색한다.
visited[i] = false; // 백트래킹을 통해 상위 경로에서 재탐색한다.
v.pop_back(); // 해당 경로 제거
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
backtracking(0);
}
|
cs |
'C++ > 알고리즘' 카테고리의 다른 글
| [C++] 알고리즘 #1 유클리드 알고리즘(Euclidean algorithm) (0) | 2023.07.06 |
|---|