[알고리즘] Backtracking

백트래킹

 

 백트래킹이란 말 그대로 '되추적'의 의미를 가진다. 즉 어떤 노드의 유망성을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가서 다른 자식 노드를 찾는 방법을 의미한다. 브루트 포스 알고리즘과 다른 점은, 모든 경우의 수 중에서 가능성이 존재하지 않는다면(=더 이상 유망하지 않다면) 더이상 탐색하지 않는다는 점이다. 이를 위해서는 상태공간트리를 그려 DFS와 같은 탐색 알고리즘을 통해서 구현할 수 있다.

 

 

 

DFS의 특징

• 자기 자신을 호출하는 순환형태의 알고리즘 형태를 가진다. (재귀 호출이 이루어진다)
• 상태공간트리에서 탐색한 노드에 대한 정보를 검사해야 한다.
• 상태공간트리에서 탐색할 노드가 유망한지를 검사해야 한다.
• 트리의 branch의 끝까지 탐색해야 다음 branch를 탐색하기 때문에 비효율적인 결과를 초래할 수 있다.

여기서 비효율적인 결과를 초래할 수 있다는 단점을 백트래킹을 이용하면 최대한 최적화할 수 있다. 백트래킹은 DFS에 '가지치기'라고 불리는 방법을 통해 노드의 유망성을 검사해서 더 이상 유망하지 않다면 그 하위 노드는 더 이상 탐색하지 않는다.

 

DFS와 백트래킹의 이해를 위해 가장 대표적인 예시인 n-Queens Problem을 예시로 들어 설명해보도록 하겠다.

 

 

 

n-Queens Problem

 

 이것은 nxn의 크기를 가지는 체스판 위에 N개의 퀸을 서로 공격할 수 없도록 배치하는 방법의 수를 말한다. 가장 간단하게 우리가 생각할 수 있는 방법은, nxn크기의 체스판에 N개의 퀸을 배치하는 경우의 수를 모두 세어 각각의 경우가 조건을 만족하는지 확인하는 방법이 있다. 

 

 

- Brute Force 방법을 사용한 구현

public class Main {

    static int cnt=0;

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

        brute_force(arr, isExist, N, 0);
        System.out.println(Main.cnt);
    }

    private static void brute_force(int[][] arr, int[][] isExist, int N, int cur) {
        if(cur==N)  {
            //check if it's a n-queens form
            //Main.cnt++; if it is
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(isExist[i][j]!=1) {
                    isExist[i][j] = 1;
                    brute_force(arr, isExist, N, cur+1);
                    isExist[i][j] = 0;
                }
            }
        }
    }
}

 가장 생각하기 쉬운 방법은 체스판에 N개의 퀸을 놓는 방법의 모든 경우의 수를 나열하여 조건을 만족하는지 여부를 체크하는 것이다. 분명히 모든 과정을 거친 후에 답을 구해낼수는 있다는 사실은 명백하지만, 모든 경우의 수를 포함해야 하는 만큼 많은 메모리와 시간을 필요로 할 수 있다.

 

 

- DFS를 이용한 탐색 알고리즘 구현

public class Main {

    static int cnt=0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] col = new int[N+1];
//        int[] used = new int[N];

        nQueens(col, N, 0);
        System.out.println(Main.cnt);
    }

    /**
     *
     * @param idx 상태공간트리에서 이번에 유망성을 검사할 depth
     */
    private static void nQueens(int[] col, int N, int idx) {
    	//유망한지 여부를 먼저 검사한다.
        if(promising(col, idx)) {
            if(idx==N) Main.cnt++;
            else
                for(int i=1; i<=N; i++) {
                    col[idx+1] = i;
                    nQueens(col, N, idx+1);
                }
        }
    }

    /**
     *
     * @param idx:상태공간트리에서 이번에 유망성을 검사할 depth
     */
    private static boolean promising(int[] col, int idx) {
        int k=1;
        boolean rst = true;
        while(k<idx&&rst) {
        	// 같은 열에 위치하거나, 대각선상에 위치하면 유망하지 않다.
            if(col[idx]==col[k] || Math.abs(col[idx]-col[k])==Math.abs(idx-k))
                rst = false;
            k++;
        }
        return rst;
    }
}

 아이디어)

체스에서 퀸은 상하좌우, 대각선에 있는 말들을 공격할 수 있다. 이 문제에서는 NxN의 체스판에 N개의 퀸을 배치하므로 열과 행마다 단 하나의 퀸만 위치할 수 있다. 위 코드에서는 기준을 행마다 하나씩 위치시켜 그 열의 번호를 나타내도록 하는 col[]로 잡아 같은 열과 대각선의 위치하지 않도록 유망함수를 설계하였다. (각 행마다 퀸이 1개씩만 배치되도록 설계했기 때문에 같은 행에 퀸이 여러개 오는 경우는 배제한다)

N=4일 경우 되추적 DFS탐색과정

이 코드에서는 nQueens함수가 재귀적으로 호출되었기 때문에 '더 이상 유망하지 않거나 끝까지 검사한 경우'를 제외하고는 가지(branch)의 끝까지 검사하게 된다. 이와 같이 유망성을 검사하며 가지의 끝까지 검사하는 방법을 DFS라고 한다.