[Algorithm 기초] 백트랙킹 (Backtracking)

백트랙킹 (Backtracking)

- 모든 경우의 수를 탐색하며 최적해를 구하는 과정에서 유망하지 않은 쪽은 더이상 구하지 않는 방법

- 돌다리 두드려보고 가는 느낌

 

용어

유망 (Promising) : 해가 될 가능성이 있는 경우 유망하다고 함

가지치기 (Pruning) : 해가 될 가능성이 없는 경우 해당 노드를 제외하는 것

백트랙킹 (Backtracking) : 유망하지 않은 쪽으로 가지 않고 되돌아 오는것

 

알고리즘 복잡도 : O(N^M)

 

 

 

//알고리즘 백트랙킹
//N-Queen 문제 (N x N 체스판에서 퀸 N개를 서로 공격할 수 없도록 배치하는 경우의 수)

public class backTracking {
    static int n = 4;
    static int[] board = new int[n];
    static int cnt;

    public static int nQueen(int row){
        if (row == n){
            cnt++;

            for (int i = 0; i < n; i++) {
                System.out.print(board[i] + " ");
            }
            System.out.println();
            return cnt;
        }

        for (int i = 0; i < n; i++) {
            board[row] = i;

            //유망한지 아닌지 체크
            if (isPromising(row)){
                nQueen(row + 1);
            }
        }

        return cnt;
    }

    public static boolean isPromising(int row){
        for (int i = 0; i < row; i++) {
            //같은 열이나 대각선에 있는 케이스에 대한 여부
            if (board[row] == board[i] || row - i == Math.abs(board[row] - board[i])){
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args)  {
        System.out.println("경우의 수 : " + nQueen(0));

    }
}