[알고리즘] 백트래킹(Backtracking)

백트래킹(Backtracking)은 조건을 만족하는 해를 찾기 위해 모든 경우를 탐색 하되, 불필요한 경우는 조기에 가지치기(pruning) 하며 탐색을 중단하는 탐색 알고리즘 이다.

즉, 선택을 번복할 수 있다는 점에서 그리디 알고리즘과 차이가 있다.

그리디 알고리즘은 항상 최적 선택 을 기준으로 해를 구성하지만, 백트래킹은 조건을 만족하는 해가 있는 방향으로만 탐색한다.

백트래킹은 상태 공간(State Space)을 트리로 나타낼 수 있을 때 적합한 방식이며, 일종의 트리 탐색 알고리즘이라고 봐도 된다.

기본적으로 DFS(Depth-First-Search) 알고리즘을 기반으로 많이 사용되며 더 볼 필요 없는 분기 를 판단하여 탐색 범위를 줄이는 조건문을 적절히 삽입함으로써 효율성을 높이는 방식이다.

대표적인 예시: N-Queens Problem

N x N 체스판 위에 N개의 퀸을 서로 공격하지 않게 놓는 문제이다.

https://www.acmicpc.net/problem/9663

보통 N = 8이 적당하며, 8을 넘어가면 시간이 오래 걸린다.

N개의 퀸의 위치를 순차적으로 결정하되, 배치될 수 있는 후보지 즉 N^2가지의 자리에서 서로 위협하지 않게 결정한다.

2차원 배열에서 퀸을 두는 모습을 상상해보자.

일단 N = 4인 경우를 생각해보자. 4 x 4 체스판에 퀸을 둘 수 있는 모든 경우의 수는 16C4로 1820가지나 된다.

하지만, 정말로 모든 경우의 수를 봐야 하는지 생각해보면 그렇지 않다. 퀸은 같은 행에 2개 이상 둘 수 없으므로 1행에 1개만 둘 수 있다. 즉 4C1 * 4C1 * 4C1 * 4C1 = 256가지 경우에서 생각해볼 수 있다.

퀸의 위치를 {i, j}라고 두면, {1, 1}, {1, 2}, {1, 3}, {1, 4}에 퀸을 둔 후 트리를 백트래킹으로 탐색할 수 있다.

여기서 더 진행할지 말지를 결정해야 하는데, 현재 상태가 모든 퀸이 서로 위협하지 않는 상태이면 더 진행한다. 만약 위협하도록 배치되었으면 진행하지 않는다.

즉, nonpromising node를 만나면 되돌아간다.

dfs로 state space tree를 탐색하되 promising한지 검사하며 탐색한다. 만약 nonpromising하다면 되돌아간다.

이제 promising 조건을 정해보자. promising이란, 현재까지의 선택이 조건을 만족하고, 향후 해가 존재할 가능성이 있을 때를 의미한다.

여기서는 새로 추가된 퀸이 다른 퀸을 위협하는지 판단하면 된다.

1 ~ k까지 배치되었고, k + 1번째 퀸을 두는 상황을 가정한다. 퀸이 놓인 열 위치를 col 배열로 관리한다. 즉 col[i]는 i번째 행의 퀸이 놓인 열의 위치이다.

우리가 조기에 같은 행에는 퀸을 2개 이상 두지 않는다고 가정했으므로, 새로 놓는 퀸의 열에 다른 퀸이 배치되어 있지 않는지 검사한다. 즉 col[i] == col[k] 인지 검사한다.

이제 남은 것은 퀸이 대각선으로 위협할 수 있는 자리에 배치된 경우인데, 대각선에 있는지 체크하는 방법은 서로에 대한 가로, 세로의 길이가 일치한지를 보면 된다.

즉 행의 차이 와 열의 차이 가 같은지 체크한다. 만약 같다면 두 퀸은 대각선에 놓인 것이다.

여기까지가 N-Queens Problem을 해결하는 일반적인 사고의 흐름이다. 이제 이 내용을 정리해보자.

• 퀸은 같은 행, 같은 열, 같은 대각선 에 있으면 안 된다.
• 모든 경우를 보는 완전 탐색으로 풀 수 있으나, 경우의 수가 기하급수적으로 증가한다.

머릿속으로 상태 공간 트리(State Space Tree)를 상상한다.

• 탐색 공간을 트리로 구성해 DFS 방식 으로 탐색한다.
• 각 노드는 현재까지 퀸을 배치한 상태 이다.
• 한 단계마다 퀸을 한 행에 배치해 나가며, 가능한 열만 탐색한다.

start
├── 1행의 각 열 시도
│ ├── 2행의 가능한 열 시도
│ │ └── ...

새로 놓은 퀸이 이전 퀸들과 같은 열 또는 같은 대각선 에 있는지 검사한다.

col[i] == col[k]           // 같은 열 체크
|col[i] - col[k]| == i - k // 같은 대각선 체크

[C++]

#include <bits/stdc++.h>
using namespace std;

int n;
int col[15]; // col[i]는 i번째 행의 퀸이 놓인 열 위치
int cnt = 0;

bool promising(int i) {
    for (int k = 1; k < i; k++) {
        if (col[i] == col[k] || abs(col[i] - col[k]) == i - k) {
            return false;
        }
    }

    return true;
}

void queens(int i) {
    if (promising(i)) {
        if (i == n) {
            cnt++;
        }
        else {
            for (int j = 1; j <= n; j++) {
                col[i + 1] = j;
                queens(i + 1);
            }
        }
    }
}

int main() {
    cin >> n;

    queens(0);

    cout << cnt;

    return 0;
}

정리

백트래킹(Backtracking)은 모든 경우를 탐색하되, 조건을 만족하지 않는 경우는 탐색을 중단한다.

N-Queens Problem은 대표적인 백트래킹 예제이다.

promising 조건을 정교하게 설정할수록 가지치기를 효과적으로 할 수 있다. 즉, 완전 탐색보다 훨씬 적은 연산으로 해를 찾을 수 있다.