Prologue

알고리즘을 푸는데 백트래킹 문제가 나왔다. 근데, 백트래킹의 정확한 의미를 잘 몰라서 간략하게 정리하려고 한다.

Subject

백트래킹

위키피디아의 정의를 보면 한정 조건을 가진 문제를 풀려는 전략이라고 나와있다. 즉, 모든 조합의 수를 살펴보는 것인데 단 조건이 만족할 때만 살펴본다.

설명을 덧붙이자면, 어떤 노드의 유망성을 점검한 후, 유망하지 않으면 그 노드의 부모 노드로 되돌아간 후 다른 자손 노드를 검색한다.

  • 유망성은 조건을 만족하는가 아닌가를 뜻한다.
  • 즉, 유망하지 않으면 배제를 하고 부모 노드로 돌아가서 풀이 시간이 단축될 수 있다.
  • DFS에서 가지치기를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법 중 하나이다.

백트래킹의 대표적인 문제는 N-Queen 문제이다. 이 문제를 통해서 백트래킹을 한 번 더 이해해보자.

N-Queen

크키가 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구해보자.

4x4를 기준으로 문제를 풀어보자. 퀸이 어떻게 이동할 수 있는지만 알면 체스가 무엇인지 몰라도 된다. 퀸은 배치된 칸을 기준으로 오와 열, 대각선 이동이 가능한 말이다.

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

이 문제를 가지치기를 하지 않는 DFS로 풀었다면 유망하지 않는 즉, 조건에 위배하는 (2,1), (2,2) 지점도 검사했을 것이다. 그러면 연산 횟수가 많아져 시간복잡도도 증가했을 것이다.

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

  1. DFS 수행 - 평소와 같이 깊이 우선 탐색인 DFS를 수행하여 노드를 찾는다.
  2. 유망한 노드 검토 - 방문한 노드를 포함해서 유망한 노드이면 서브트리(하위노드)로 이동하고 그렇지 않으면 백트래킹을 수행하낟.
  3. 방문한 노드의 하위 노드로 이동하여 다시 재귀를 통해 DFS를 수행한다.
  4. 백트래킹 수행 - 방문한 노드를 가지치기를 하고 상위 노드로 백트래킹한 후 DFS를 다시 수행한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

import java.util.Scanner;

/**
 * 22/05/2019
 * 완탐 : N-Queen
 * 백트래킹의 대표적인 문제.
 */
public class Main {
    private static int N = 0;
    private static int count = 0;

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

        for (int i = 1; i <= N; i++) {
            int[] column = new int[N + 1]; // N행 까지 담기 위해. index -> 행, value -> 열.
            column[1] = i; // 1행 i열에 퀸을 놓음.

            // 1. DFS 수행.
            // 1행 i 열에 퀸을 놓았을 경우 dfs 로 가능한 경우를 확인한다.
            dfs(column, 1);
        }

        System.out.println(count);
    }

    private static void dfs(int[] column, int row) {
        // row 와 N 이 같다는 말은 N 번째 행까지 퀸을 놓았다는 의미이다.
        // 즉, 퀸을 다 놓았다는 말! 따라서 count 를 증가시킨다.
        if (row == N) {
            count++;
        } else {
            for (int i = 1; i <= N; i++) {
                column[row + 1] = i; // (row+1)행 i열에 퀸을 놓는다.

                // 2. 유망한 노드인지 판단.
                if (isPossible(column, row + 1)) {
                    // 3. 서브 트리로 이동.(해당 노드의 하위 노드)
                    dfs(column, row + 1);
                }else {
                    // 4. 백트래킹 수행. 해당 노드는 가지치기 됨.
                    // 아니면 백트래킹. 0이면 퀸을 못놓는다는 의미.
                    column[row+1] = 0;
                }
            }
        }
        column[row] = 0;
    }

    private static boolean isPossible(int[] column, int row) {

        // (row+1)이 들어오는데 그 전까지 즉, row 행 전까지 검사한다.
        for (int i = 1; i < row; i++) {

            // i 행과 row 행의 열이 같으면 퀸을 놓을 수 없다.
            if (column[i] == column[row]) {
                return false;
            }
            // i 행과 row 행의 열 값이 대각선 위치에 존재하면 퀸을 놓을 수 없다.
            if (Math.abs(i - row) == Math.abs(column[i] - column[row])) {
                return false;
            }

        }
        // 위의 경우가 모두 된다면 true 반환한다.
        return true;

    }
}

참고