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

백트래킹

기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다' 는데 기본 아이디어가 있다. 대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색) 이 있다. DFS 는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동한다. DFS 의 장점은 무한히 깊은곳을 찾아야할때 효과적이다. 하지만 DFS 는 모든곳을 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할수도 있다.

그래서 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다. 백트래킹은 DFS에 가지치기 (Pruning) 를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법이다. 가지치기를 얼마나 잘하느냐에 따라서 효율이 극대화 될수 있는 방법이다.

뭔말이지 하는 사람도 있을껀데 어쨋든 우리가 알아야할것은 "배제", "풀이 시간 단축" 이다. 이론보다는 예시로 설명하는 것이 더 이해가 잘될것 같다. 구글 검색창에 백트래킹이라고 검색하면 항상 딸려오는 대표 예제인 n-queen 으로 백트래킹을 설명하겠다.

N-Queen

백트래킹 하면 바로 이문제라고 알려져 있을 정도로 유명하다고 한다. 문제는 아래와 같다.

크기가 N * N 인 체스판 위에 퀸 N 개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

4 * 4 를 기준으로 문제를 풀어보자. 체스를 모르는 사람도 풀수 있는 문제다. 퀸은 배치된 칸을 기준으로 오와 열, 대각선 이동이 가능한 말이다. 아래의 사진을 보면 이해가 될것이다.

빨간색 선이 퀸이 이동할수 있는 경로이고, 첫번째 퀸과 공격할수 없게 배치할려면 2번째 줄은 2, 3 번째 위치에 퀸을 놓아야 된다. 첫번째 퀸의 위치를 (1, 1) 로 하면 트리구조는 다음과 같다.

만약 이문제를 가지치기 하지않는 DFS 로 풀이했다면 유망하지 않는 (2, 1), (2, 2) 지점도 검사를 했을것이다. 그렇게되면 더큰 체스판에서 퀸을 놓는 경우의 수를 찾을때 수많은 연산이 일어나게된다.

그래서 우리는 가지치기를 잘해야한다! 백트래킹은 크게 4가지 절차로 구성되어 있다.

DFS 수행 - 유망한 노드 검토 - 서브 트리 이동 - 백트래킹 수행

1. DFS 수행 - 먼저 평소와 같이 깊이우선탐색인 DFS 를 수행하여 노드를 찾는다.
2. 유망한 노드 검토 - 방문한 노드를 포함해서 유망한 노드이면 서브트리로 이동하고 그렇지 않으면 백트래킹을 수행한다.
3. 방문한 노드의 하위 노드로 이동하여 다시 재귀를 통해 DFS 를 수행한다.
4. 백트래킹 수행 - 방문한 노드를 가지치기를 하고 상위 노드로 백트래킹 한 후 DFS 를 다시 수행한다.

이절차를 통해서 2번째 위치에 퀸을 놓는 방법을 생각해보자.

1. (1, 1) 에서 시작하여 DFS 수행을 통해 가장 첫번째 노드인 (2, 1) 지점으로 간다.
2. (2, 1) 노드를 검사해보니 첫번째 퀸의 이동반경에 포함되기 때문에 유망한 노드가 아니어서 백트래킹을 수행하여 상위 노드인 (1, 1) 지점으로 이동한다.
3. 다시 DFS 를 수행하여 다음 노드인 (2, 2) 로 이동한다.
4. (2, 2) 노드를 검사해보니 첫번째 퀸의 이동반경에 포함되기 때문에 유망한 노드가 아니어서 백트래킹을 수행하여 상위 노드인 (1, 1) 지점으로 이동한다.
5. 다시 DFS 를 수행하여 다음 노드인 (2, 3) 로 이동한다.
6. (2, 3) 노드를 검사해보니 첫번째 퀸의 이동반경에 포함되지 않아서 유망한 노드가 되었다. 이제 (2, 3) 을 기준으로 DFS 를 수행하여 3번째 퀸의 위치를 찾는다.

이렇듯 가지치기를 통해서 해당 노드가 유망하지 않으면 가차없이 짤라버려서 탐색하는 경로를 최소한으로 줄일수 있게 된다.

그럼 이제 n-queen 문제를 코드로 구현해보자!

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);
}

main 부터 보면 체스판의 크기인 n 과 (최대 크기를 15로 지정) 행의 좌표를 담을 col 배열이다. for 문을 돌아서 첫번째 지점인 (1, 1) 부터 검사를 한다. col 배열의 인덱스값은 열이고 i는 행의 값이다. 처음에는 col[1] = 1 이 담기기 때문에 첫번째 줄에 배치되는 퀸의 위치는 (1, 1) 이 된다. 다음 백트래킹의 첫번째 절차인 DFS 를 수행하여 다음 노드로 이동한다.

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;
            }
        }
    }
}

dfs 메서드는 현재 노드를 검사하여 유망하면 하위 노드로 이동하고 그렇지 않으면 백트래킹을 수행하여 해당 노드를 가지치기 한다. 먼저 현재 도착한 노드의 좌표를 저장한다. 그리고 두번째 절차인 유망한 노드인지를 검토를 하고 유망하면 서브트리로 이동하기 위해 DFS 를 재수행하고 그렇지 않으면 백트래킹을 수행하여 해당노드를 가지치기 한다. 마지막으로 해당 열값을 체스판의 크기를 초과하면 마지막 노드까지 탐색이 완료되었기 때문에 정답 카운트를 1증가 시킨다.

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;
}

마지막으로 해당 노드가 유망한 노드인지 확인하는 isPossible 메서드다. 첫번째 열부터 해당 노드까지 for 문을 돌아서 같은 행에 퀸이있는지, 대각선에 퀸이 있는지를 찾아본다. 검사를 모두 마치고 검사를 통과했다면 true를 반환하여 다음 절차인 서브트리로 이동할수 있게 된다.

실행한 결과는 아래와 같이 나왔다. 4 * 4 크기의 체스판에서 4개의 퀸을 놓을수 있는 경우의 수는 총 2가지로 나오게 된다.

4
2

아래는 전체 코드다.

import java.util.Scanner;

public class test {

    static int col[];
    static int n;
    static int ans;

    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;
    }
}