[알고리즘] 7. Backtracking

이전 내용

[알고리즘] 6. Dynamic Programming

 

 

 

1. Brute force

2. Divide and conquer
3. Decrease and conquer
4. Transform and conquer
5. Greedy Method
6. Dynamic Programming
7. Backtracking
8. Branch and Bound

여기서는 Backtracking에 대해 다룬다.

 

---

Backtracking이란

• DFS인데 조건이 있어서 중간에 과정을 점프할 수 있는 느낌이다.
• 단계적으로 문제 해결하다가 해결 방법 없으면 되돌아 간다.
• 직전 선택에 대한 되추적이다.
• 모든 경우의 수를 고려하나 이미 가망 없는 건 건너뛸 수 있다.

 

---

Backtracking 예시

1. Solving a Maze
2. Coloring a Map (Graph Coloring)
3. n-Queens Problem
4. Hamiltonian Circuits

---

Solving a Maze

#include <iostream>
#include <vector>
using namespace std;


int maze[5][5] = {
    {1, 1, 0, 1, 1},
    {0, 1, 0, 1, 0},
    {1, 1, 1, 1, 0},
    {0, 1, 0, 1, 0},
    {1, 0, 1, 1, 1}
};
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
vector<pair<int, int>> path;

bool findPath(int x, int y, int fx, int fy, bool visited[5][5]) {
    if (x == fx && y == fy) {
        path.push_back({x, y});
        return true;
    }
    visited[x][y] = true;
    path.push_back({x, y});

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5 && maze[nx][ny] && !visited[nx][ny]) {
            if (findPath(nx, ny, fx, fy, visited)) return true;
        }
    }

    path.pop_back();
    return visited[x][y] = false;
}

int main() {
    int sx, sy, fx, fy;
    cout << "Start position: ";
    cin >> sx >> sy;
    cout << "End position: ";
    cin >> fx >> fy;

    bool visited[5][5] = {}; 
    if (findPath(sx, sy, fx, fy, visited)) {
        cout << "Path found:\n";
        for (auto [x, y] : path) cout << "(" << x << ", " << y << ") ";
        cout << endl;
    } else {
        cout << "No path found." << endl;
    }
    return 0;
}

• branch and bound 의 대표적인 방식인 미로찾기 문제다. 상하좌우 중 안가본 길을 탐색하고, 막혀있으면 해당 분기는 삭제된다.
• 하지만 현재 있는 위치에 걸어온 길이 있을것임으로 무조건 한칸은 방문했던 곳이라 실질적으로는 최대 3방향 탐색만 하면 된다.
• 재귀식을 사용한 DFS의 방식과 유사하다. 사실 DFS와 backtracking은 완전히 대비되는 것이 아니여서, 여기서는 사실상 DFS를 사용해서 작성했다고 봐도 무방하다.

 

---

Coloring a Map

• 4색정리로 증명된 최소 색깔로 인접노드 칠하기 문제도 백트래킹 문제라고 볼 수 있다.
• 각 면을 노드로, 인접한 것은 무방향 그래프로 연결할 수 있다. 
• 어떤 지도든 4가지 색으로 다 칠할수 있으므로, 칠하다가 conflict가 나면 이전에 칠했던 상황으로 돌아가 선택을 바꾸는 식으로 backTracking이 적용된다.

---

 

N-Queens Problem

#include <iostream>
using namespace std;

int col[8];

bool check(int x){
    for(int i=0; i<x; i++){
        if(col[i]==col[x] || abs(col[i]-col[x])==x-i){
            return false;
        }
    }
    return true;
}


void nqueen(int x){
    if(x==8){
        for(int i=0; i<8; i++){
            printf("(");
            printf("%d,%d",i,col[i]);
            printf(") ");
        }
        printf("\n");
    }
    else{
        for(int i=0; i<8; i++){
            col[x]=i;
            if(check(x)){
                nqueen(x+1);
            }
        }
    }
}


int main(){
   nqueen(0);
}

• 유명한 문제인 N-queen 문제이다.
• 정사각형 체스판 위 가로, 세로, 대각선에 퀸이 겹쳐서는 안된다. N>=4 부터 답이 있고, 여기서는 8일때를 기준으로 답을 삼았다.
• 2차원 배열을 사용하여 풀수도 있지만, 1차원만 사용해도 충분히 답을 낼 수 있다. 1차원 배열에서 각 index가 가로축의 숫자이고, 그 안에 들어있는 값이 세로의 위치 값인 것이다. 이는 모든 가로열에 하나씩 퀸이 배치되므로 가능하다.
• 또한 abs 공식을 이용해 대각선의 위치까지 확인해 비교적 간단하게 코드를 짤 수 있다.

 

---

Hamilitonian circuits

• Hamiltonian Path는 단순히 모든 노드를 한번씩만 방문하면 되고, Hamiltonian Circuit은 여기에 출발지와 도착지가 같아야 한다는 조건이 추가된다.
• 알파벳 순서대로 확장해 나가며, 막히면 백트래킹으로 되돌아 간다. 
• 여행자 문제와 유사하다.

 

---

 

결론

Backtracking에 관한 내용이었다.

 

이어지는 내용

[알고리즘] 8. Branch and Bound