백 트래킹 (Back Tracking)

백트래킹 이해

• 제약 조건 만족 문제에서 해를 찾기 위한 전략
  • 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약조건을 만족할 수 없다고 판단되는 즉시 backTrack(다시는 이 후보군을 체크하지 않을것을 표기)하고, 바로 다음 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법이다
• 실제 구현시 고려할 수 있는 모든 경우의 수 (후보군)을 상태 공간 트리(State Space Tree)를 통해 표현
  • 각 후보군은 DFS방식으로 확인한다
  • 상태 공간 트리를 탐색하면서, 제약이 맞지않으면 해의 후보가 될만한 곳으로 넘어가서 탐색한다
    - Promissing (유망성 판단) : 해당 루트가 조건에 맞는지를 검사하는 기법
    - Pruning (가지치기) : 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법

    즉, 백트래킹은 트리 구조를 기반으로 DFS로 깊이 우선 탐색을 진행하면서 각 루트에 대해서 조건이 부합하는지 Promissing(유망한지) 보고, 만약 해당 트리에서 조건에 맞지않는 노드는 더이상 DFS로 탐색하지 않고, 가지를 쳐낸다(Pruning)

N-Queen 문제

대표적인 백트래킹 문제로 N*N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제
퀸은 수직, 수평, 대각선 방향으로 이동(공격)이 가능하다

수직체크 & 대각선 체크를 진행한다 (수평체크는 어짜피 한 행에 하나만 놓으면되므로 검사하지 않는다)

수직체크

• 같은 열에 있다면 제외

대각선 체크

• 만약 행과 행의 차이 == 열과 열의 차이라면 같은 대각선에 있는것이므로 제외

public class N_Queens {
    static int[] result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] Ns = br.readLine().split(" ");
        int N = Integer.parseInt(Ns[0]);

        // 모든 행을 채운 결과
        result = new int[N];
        //각 행을 채운 결과를 담는곳
        List<Integer> current_candidate = new ArrayList<>();
        DFS(N, 0, current_candidate);
    }
    private static void DFS(int N, int current_row, List<Integer> current_candidate) {
        if (current_row == N){
            for (int i = 0; i < current_candidate.size(); i++){
                result[i] = current_candidate.get(i);
            }
            Arrays.stream(result).forEach(s -> System.out.print(s+" "));
            System.out.println();
        }
        else {
            for (int current_col = 0; current_col < N; current_col++){
                if (is_available(current_candidate, current_col)){
                    current_candidate.add(current_col);
                    DFS(N, current_row + 1, current_candidate);
                    //조건에 부합되지 않거나 N개를 모두 채운 경우 하나씩 빼주면서 backTracking해준다
                    current_candidate.remove(current_candidate.size() - 1);
                }
            }
        }
    }

    private static boolean is_available(List<Integer> candidate, int current_col) {

        int current_row = candidate.size();
        for (int queen_row = 0; queen_row < current_row; queen_row++){
            if (candidate.get(queen_row) == current_col
            || Math.abs(candidate.get(queen_row) - current_col) == current_row - queen_row){
                return false;
            }
        }
        return true;
    }
}