Notice
Recent Posts
천천히 빛나는
알고리즘 : 백트래킹 (Back-tracking) + 조합, 순열 (C++ 구현) 본문
백트래킹 (Back-tracking)
정답을 찾는 도중에 막히면 더 이상 깊이 들어가지 않고 이전 단계로 돌아가서 정답을 찾는 방법
깊이 우선 탐색 DFS는 가능한 모든 경로를 탐색한다. 불필요할 것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 줄이지 못한다.
백트래킹은 지금 경로가 정답이 아닐 것 같다면 이전 단계로 돌아가므로 DFS보다 효율적이다. 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 탐색하는 것이 백트래킹이다.
문제풀이에서는 모든 경우의 수를 탐색하는 과정에서 (DFS 등으로 구현) 조건문으로 절대 답이 될 수 없는 상황을 설정하고 그런 상황이 되었을 때는 탐색을 중지시킨 뒤 다시 이전 단계로 돌아가서 탐색하도록 구현할 수 있다.
백트래킹 예시
bool visited[20];
int n, r;
void dfs(int cnt, int idx) { // 현재까지 결과, 탐색 진행할 인덱스
// 조건에 해당할 때 중기
if (cnt == r) {
for (int i = 0; i < n; i++)
{
if(visited[i]==1)
cout << i << " ";
}
cout << '\n';
return;
}
for (int i = idx; i < n; i++) {
if (!visited[i]) {
visited[i] = true;
dfs(cnt + 1, i);
visited[i] = false; // 다시 돌아갈 수 있도록
}
}
}
int main() {
n = 4;
r = 2;
dfs(0, 0);
}
n개 중 순서를 고려하지 않고 r개를 선택하는 조합 코드이다. 자세한 코드 설명은 아래에서 하도록 하겠다.
1. 조합
가장 처음으로 뽑을 index가 정해지면 그 이후 전으로 돌아갈 필요가 없다. 화살표 방향이 오른쪽을 향하는 것이다.
void dfs(int idx, int cnt) {
if (cnt == k) {
for (int i = 0; i < v.size(); i++)
{
if (visited[i] == 1)
cout << v[i] << " ";
}
cout << '\n';
return;
}
for (int i = idx; i < n; i++) // 선택될거 결정
{
if (visited[i] == 1) // 이미 방문
continue;
visited[i] = 1;
dfs(i, cnt + 1);
visited[i] = 0; // {1, 2, 5}이 끝났다면 {1, 3, 5}에서도 5가 선택될 수 있도록
}
}
int main() {
cin >> n >> k; // nCk = n개 중에 k 선택
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
v.push_back(x);
}
dfs(0, 0);
}
중복을 허용하지 않는 조합이다.
vector <int> v;
vector <int> temp;
int n, k;
void dfs(int idx, int cnt) {
if (cnt == k) {
for (int i = 0; i < temp.size(); i++)
{
cout << temp[i] << " ";
}
cout << '\n';
return;
}
for (int i = idx; i < n; i++) // 선택될거 결정
{
temp.push_back(v[i]);
dfs(i, cnt + 1);
temp.pop_back(); // {1, 2, 3}이 끝났다면 {1, 2, 4}가 될 수 있도록
}
}
int main() {
cin >> n >> k; // nCk = n개 중에 k 선택
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
v.push_back(x);
}
dfs(0, 0);
}
중복조합에서는 visited 배열 없이 vector로만 구현하면 된다.
2. 순열
순열은 조합과 다르게 거꾸로 갈 수도 있다. 순서를 고려하기 때문이다. idx 변수가 필요하지 않는 것이다.
void dfs(int idx, int cnt) {
if (cnt == k) {
for (int i = 0; i < temp.size(); i++)
{
cout << temp[i] << " ";
}
cout << '\n';
return;
}
for (int i = 0; i < n; i++) // 선택될거 결정
{
if (visited[i] == 1)
continue;
visited[i] = 1;
temp.push_back(v[i]);
dfs(i, cnt + 1);
visited[i] = 0;
temp.pop_back();
}
}
int main() {
cin >> n >> k; // nCk = n개 중에 k 선택
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
v.push_back(x);
}
dfs(0, 0);
}
여기서 visited를 없애면 중복 순열이 된다.
코드가 이해가 되지 않는다면 아래 티스토리를 읽어보는 걸 적극 추천한다! 정말 설명을 잘해두셨다. 사진도 여기에 있는 걸 참고하였다.
https://charles098.tistory.com/9
'STUDY > ALGORITHM' 카테고리의 다른 글
알고리즘 : 다이나믹 프로그래밍 (Dynamic Programming) (2) - 기초 문제 풀이 (C++로 구현) (0) | 2023.10.20 |
---|---|
알고리즘 : 다이나믹 프로그래밍 (Dynamic Programming) (1) (0) | 2023.10.19 |
알고리즘 : DFS와 BFS (3) - 기초 문제 풀이 (C++로 구현) (0) | 2023.10.07 |
알고리즘 : DFS와 BFS (2) - BFS (C++로 구현) (1) | 2023.10.06 |
알고리즘 : DFS와 BFS (1) - DFS (C++로 구현) (0) | 2023.10.06 |