[알고리즘] 백트래킹

백트래킹

백트래킹이란, 여러 후보해 중 특정 조건을 충족시키는 모든 해를 찾는 알고리즘이다. 

백트래킹의 목적은 해가 될 조건을 만족시키는 "진짜 해"를 효율적으로 찾는것이 백트래킹의 목적이다.

백트래킹은 탐색을 진행하다가 더 갈 수 없게되면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 이런 이름이 붙었고,

주로 재귀적으로 구현한다.

 

'모든 해'란, 예를 들어 탈출로가 두개인 미로 문제를 생각해보자. 이러한 미로에서 탈출할 수 있는 최단 경로는 2개가 존재한다. 이 2개 해를 일컬어 '모든 해'라고 한다.

'후보 해' 란, 해가 될 수 있는 가능성을 가진 부분해의 조합이다. 

 

백트래킹은 DFS를 빼고 이야기 할 수 없는 알고리즘이다. DFS는 백트래킹의 골격을 이루는 알고리즘이다.

백트래킹은 DFS 방식으로 탐색하는 모든 방법을 뜻하기도 한다. 백트래킹 알고리즘마다 DFS에서 조금씩 변형은 일어나지만 기본적으로 모두 DFS의 범주에 속한다. 백트래킹 알고리즘이 상태 공간 트리를 명시적으로 만드는 것은 아니지만, 알고리즘의 진행 과정은 상태  공간 트리의 루트에서 시작해서 DFS 방식으로 탐ㅅ색을 해나가는 것과 대응된다.

 

 

- 백트래킹이 동작하는 방식

 

1. 백트래킹은 상태공간트리에서 DFS를 실시한다.

    (상태공간트리 : 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리)

2. 이때 이 노드가 유망한 노드인지, 즉 해가 될 가능성이 있는 노드인지, 확인한다.

3. 유망한 노드라면, 그 자식 노드를 계속하여 검색해나간다.

4. 유망하지 않다면, 자식 노드를 검색하지 않고 중단한다.

 

 

1. 미로 찾기 문제

백트래킹의 쉬운 예를 한번 살펴보자.

 

아래의 왼쪽 그림은, Start가 시작지점이고 Goal이 목표지점이다. 그리고 나머지 점들은, 미로를 탐색하다가 선택을 해야하는 지점, 즉 분기점은 정점으로 나타낸 것이다. 

오른쪽 그림은, 이 미로의 탐색과정을 상태공간 트리로 나타낸 것이다.

 

출처 : http://www.jidum.com/jidums/view.do?jidumId=513

오른쪽 그림은 조금더 상세하게 살펴보자.

• 정점 S에서 시작해 정점 1로 이동한다. 정점 1에서는, 정점2와 정점3 중 하나를 선택할 수 있다.
• 임의로 정점 2로 갔다. 도착하니 더이상 갈 곳이 없다.
• 정점 2로 가는데 거쳤던 정점 1로 다시 되돌아 온다. 이제 남은 선택지는 정점3뿐이니 정점 3으로 이동한다.
• 정점 3도 두가지 선택지가 있다. 임의로 정점 4를 선택했다.
• 정점 4도 두가지 선택지가 있다. 임의로 정점 5를 선택했다.
• 정점 5도 두가지 선택지가 있다. 임의로 정점 6을 선택했다.
• 정점 6은 정점7, 8, 9 세가지가 있다. 각각 한번씩 가보면 모두 갈 곳이 없기 때문에 다시 정점 6으로 돌아온다.
• 정점 6도 다시 정점 5로 되돌아간다. 이제 남은 선택지는 정점 G뿐이다.
• 정점 G에 가보니 목표 지점임을 알게 된다. 탐색을 종료한다.

미로 찾기를 구현한 알고리즘을 살펴보자.

maze(v) { // v는 정점
    visited[v] = YES;
    if(v = T) then {return "성공";} // T는 목표지점
    for each x ∈ L(v) // L(v)는 정점 v와 인접한 정점의 집합
    	if (visited[x] = NO) then {
        	prev[x] <- v;
            maze(x);
         }
 }        

알고리즘이 종료된 후, 정점 S에서 G까지의 경로를 알려면 G에서 시작해 prev[]를 통해 따라가면 S에 이르게 된다. 이의 역방향이 해답 경로이다. 이 문제는 사실상 DFS와 같다.

 

2. N - Queen

N-Queen 문제는, 크기가 N*N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

 

파란선이 퀸이 움직일 수 있는 경로이고, 첫번째 줄에 있는 퀸과 공격할 수 없게 배치하려면 두번째는 3,4번째 칸에 퀸을 놓아야한다. 첫번째 퀸의 위치를 (1,1)로 할 때 트리 구조를 살펴보자.

 

출처 : https://thd0011.tistory.com/19

이 문제는 백트래킹과 DFS 방식으로 모두 풀 수 있다. 두 방식으로 풀었을 때의 가장 큰 차이점은, 

DFS는 전체 모든 경우의 수를 모두 확인하고, 백트래킹은 유망한 노드인 경우에만 탐색을 한다는 것이다.

체스판이 4 * 4가 아니라 더 커진다면 DFS와 백트래킹의 연산의 횟수는 점점 차이가 많이 날 것이다.

 

이 트리 구조를 보면서, 두번째 퀸은 어느 위치에 놓아야하는지 생각해보자.

1. (1,1)에서 시작하여 DFS를 이용해 첫번째 노드인 (2,1)를 방문한다.    2. (2,1)의 위치를 보면, 첫번째 퀸의 이동반경에 포함되어 있다. 그러므로 이 노드는 유망하지 않은 노드이고, 이 노드 아래는 더이상 살펴보지 않아도 된다. 백트래킹을 이용해 (1,1)로 다시 돌아간다.   3. (2,2)로 이동한다. 하지만 (2,2) 역시 첫번째 퀸의 이동반경 내에 있다. 유망하지 않은 노드이니 다시 (1,1)로 백트래킹해 올라간다.   4. 다시 DFS를 이용해 (2,3)으로 이동한다. 첫번째 퀸의 이동경로에 포함되지 않는다. 따라서 이 노드는 유망 노드이다.   5. 이제 (2,3)을 기준으로 다시 DFS를 수행하여 세번째 퀸의 위치를 찾는다.

 

코드를 살펴보자.

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();

    for (int i = 1; i <= n; i++) {
        // 첫번째 퀸의 시작점은 행을 기준. (i = 1) => (1, 1), (i = 2) => (1, 2), (i = 3) => (1, 3)
        col = new int[16];
        col[1] = i;

        // 1. DFS 수행 (다음 열인 2열 이동)
        dfs(2);
    }
    System.out.println(ans);
}

static void dfs(int row) {
    // 체스판 범위를 넘어선 경우
    if (row > n) {
        ++ans;
    } else {
        for (int i = 1; i <= n; i++) {
            // 현재 위치하고 있는 노드의 좌표를 저장 (row: 열, i: 행)
            col[row] = i;

            // 2. 유망한 노드 검토
            if (isPossible(row)) {
                // 3. 서브 트리 이동 (해당 노드의 하위 노드)
                dfs(row + 1);
            } else {
                // 4. 백트래킹 수행, 해당노드는 가지치기 되어진다.
                col[row] = 0;
            }
        }
    }
}

static boolean isPossible(int c) {
    // 이전 열들을 탐색하면서 유망한 노드인지 확인
    for (int i = 1; i < c; i++) {
        // 상위 노드에서 같은 행에 퀸이 있는지 여부
        if (col[i] == col[c]) {
            return false;
        }
        // 대각선 검사, 상위 노드의 퀸과 현재 노드의 퀸의 가로 세로 거리가 같은지 검사
        if (Math.abs(col[i] - col[c]) == Math.abs(i - c)) {
            return false;
        }
    }
    return true;
}

 

---

◎ 참고자료

thd0011.tistory.com/19

https://thd0011.tistory.com/19

쉽게 배우는 알고리즘 - 백트래킹(478p - 480p)