[알고리즘/C++] - 백트래킹(Backtracking)

길을 찾아보아요

안녕하세요 오늘은 백트래킹 알고리즘에 대해서 알아보도록 하겠습니다..

약간 지침이슈

---

뒤를 추적한다,,?

맞습니다! 알고리즘들은 이름들이 참 직관적이네요~

백트래킹(Backtracking)

: 정답이 아니라고 판단되면 다시 되돌아가서 답을 찾는 기법으로, 답을 얻을때까지 모든 가능성을 탐색하는 알고리즘

 

백트래킹은 얼핏보면 설명처럼 모~든 가능성을 탐색한다는 것만 보고 브루트포스(완전탐색)과 다를 바 없다고 생각할지도 모릅니다. 확실히 최악의 경우 모든 가능성을 검색하기 때문에 브루트포스와 같은 실행속도를 가지고 있을 수 있습니다.

하지만 백트래킹은 검사한 하나의 내용만으로 답이 될 수 없는 다른 내용들을 사전에 배제하며 검사합니다. 그렇기 때문에 특정 상황에서 쓰인다면 브루트포스보다 확실하게 빠르고 효율적인 알고리즘입니다.

 

말로 설명하려니 백트래킹의 개념을 설명하기가 쉽지 않은 것 같습니다..

이 백트래킹의 개념은 트리 구조에서 설명하기가 굉장히 편합니다.

 

잘그렸어요

자.. 이 구조는 2차원 배열 [2][2]를 트리로 구조화한 모습입니다.

그리고 이 구조에서 [1][1]을 찾고자합니다.

이 과정에서 백트래킹을 이용하면 어떻게 동작하는지 알아보겠습니다.

 

1. 가장 왼쪽노드부터 확인해봅니다.

[0][n]노드입니다. 우리가 찾고하자는 [1][n]배열이 아니기 떄문에 한번에 왼쪽 노드들은 한번에 배제되고(가지치기), 다시 루트 노드로 돌아옵니다.\

2. 다음 차례로 오른쪽 노드를 확인했습니다. 

저희가 찾던  [1][n]입니다! 

3. 내려온 노드에서부터 다시 왼쪽부터 확인해봅니다. 저희가 찾고자하는 값이 아니군요ㅠㅠ 다시 상위 노드로 돌아옵니다.

4. 오른쪽 노드를 확인합니다. 

와우~ 저희가 찾던 그 값입니다!!

 

 

백트래킹 구현 방법 및 알고리즘 예제

백트래킹은 여러가지 방법으로 구현이 가능합니다. 대표적인 세가지 방법을 소개시켜 드리도록 하겠습니다.

1. DFS로 백트래킹 구현하기

가장 대표적인 방법은 백트래킹 구현 방법입니다. 그리고 그 중 가장 쉬운 예는 순열이라고 할 수 있겟습니다.

아래는 순열을 백트래킹으로 구현한 예시입니다.

방문여부를 체크하고 재귀를 통해 가능한 순열을 생성합니다.

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<bool> visited;
vector<int> path;

void dfs(int depth) {
    if (depth == N) { //n에 도달한 경우
        for (int num : path) cout << num << " "; //경로 보여주기
        cout << "\n";
        return; //종료
    }
    for (int i = 1; i <= N; ++i) { //1부터n까지의 숫자 탐색
        if (!visited[i]) {사용하지 않은 숫자인 경우
            visited[i] = true; //사용체크
            path.push_back(i); //경로에 추가
            dfs(depth + 1); //다음 깊이로 탐색
            path.pop_back(); //경로에 제거
            visited[i] = false; //사용해제
        }
    }
}

int main() {
    cin >> N;
    visited.resize(N + 1, false);
    dfs(0);
    return 0;
}

2. BFS로 백트래킹 구현하기

이번 BFS예제도 순열을 구하는 것으로 예를 들어보았습니다. 아까 말한것처럼 기본적인 백트래킹은 DFS로 구현하게 됩니다. 다만, 예외적으로 답이 깊지 않을 것으로 예상되는 경우거나, 최단경로 등의 문제를 해결할 때에는 간혹 BFS로 백트래킹을 구현하는 경우가 더욱 효율적일 때도 있습니다.

#include <iostream>
#include <queue>
#include <vector>
#include <set>

using namespace std;

int N; // 사용할 숫자의 개수

int main() {
    cin >> N;

    // BFS를 위한 큐: 각 상태는 (현재까지의 순열 경로, 사용한 숫자 집합)으로 구성
    queue<pair<vector<int>, set<int>>> q;
    q.push({{}, {}}); // 초기 상태: 빈 경로, 빈 사용 집합

    while (!q.empty()) {
        // 큐에서 하나의 상태 꺼내기
        auto [path, used] = q.front();
        q.pop();

        // 만약 경로의 길이가 N이라면, 완성된 순열이므로 출력
        if (path.size() == N) {
            for (int num : path) cout << num << " ";
            cout << "\n";
            continue;
        }

        // 1부터 N까지 숫자 중 아직 사용하지 않은 숫자를 추가해 새 상태 생성
        for (int i = 1; i <= N; ++i) {
            if (used.find(i) == used.end()) { // i가 아직 사용되지 않았다면
                vector<int> new_path = path; // 기존 경로 복사
                set<int> new_used = used;    // 기존 사용 집합 복사
                new_path.push_back(i);       // 숫자 i 추가
                new_used.insert(i);          // 숫자 i 사용 표시
                q.push({new_path, new_used}); // 새로운 상태 큐에 추가
            }
        }
    }

    return 0;
}

3. 최선 우선 탐색

이 방법 또한 전형적인 유형보다는 특정 유형에서 사용되는 경우입니다. 이 방법의 경우는 따로 코드를 첨부하지는 않았습니다. 아직 최선 우선 탐색이나 이 방법에서 사용되는 휴리스틱 등의 개념을 블로그에서 다루지 않았기 때문입니다.. 요 방법은 선행적인 알고리즘 글을 올린 후에 정리해보려고 합니다!

 

 

백트래킹의 활용 

백트래킹은 다양한 문제들에 활용됩니다.

부분 수열 합
순열 및 조합 생성
미로 찾기
스도쿠 판 채우기

 

위의 설명이 이해가 되었다면 예시만 봐도 대충 어떤 방식으로 알고리즘이 작동될 지 예상이 갈거라고 생각합니다 ㅎㅎ

생각해보니 저도 어릴적 스도쿠를 하며 무의식중에 머릿속에서 백트래킹을 해왔던 거군요..!!

---

이렇게 백트래킹의 개념에 대해서 알아보았습니다.

저는 백트래킹이 사실 개념적으로는 어찌 이해가 되지만 막상 실전에가면 알고리즘을 작성하는 데에 애를 먹었던 것 같습니다.

그러고보니 코드 설명을 제대로 안 쓴 것 같네요 ,, 시간이 나면 다시 돌아와서 보충해보겠습니다

 

https://solved.ac/problems/tags/backtracking

solved.ac

그럼 오늘도 저는 이만 물러납니다

총총