[백준/자바] 백트래킹 9663번 - N-Queen

• 문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

 

 

※ 체스 규칙 상 퀸은 직선, 대각선으로 이동 가능함

= 같은 행, 열, 또는 대각선상에 놓인 퀸은 서로 공격 가능

 

 

• 해결

 

• 백트래킹

 

 

백트래킹은 탐색 조건이 있는 DFS라고 볼 수 있다.

DFS 과정에서 조건에 부합하는 노드는(promising) 계속 탐색하고, 조건에 부합하지 않는 노드는 탐색에서 배제한다(pruning). 

 

1. promising(유망한)

조건에 부합하는 노드일 때 유망하다고 한다. promising 검사에서 통과 시(조건에 부합할 때) 다음 depth로 넘어가 DFS 탐색을 계속한다.

 

2. pruning(가지치기)

유망하지 않은 노드를 만나면 해당 노드를 배제하고 이전 depth로 돌아간다.

 

 

• 코드

public class NQueen {
    // N x N 의 체스판에 N개의 퀸들을 서로 공격할 수 없는 위치에 놓는 경우의 수 세기
    // 퀸 => 대각선, 상하좌우에 위치하면 공격 불가

    private static int N;
    private static int[] array; // 퀸 위치 (행 = 인덱스, 열 = 값)
    private static int count; // 퀸들이 서로 공격할 수 없는 위치에 있는 경우의 수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        array = new int[N];

        nQueen(0);

        System.out.println(count);
    }

    private static void nQueen(int row){ // 행 탐색
        // 마지막 행까지 탐색 완료
        if (row == N) {
            count++;
            return;
        }

        for (int col=0;col<N;col++){ // 열 탐색
            array[row] = col; // 좌표 저장

            if (promising(row)){ // 저장된 좌표 탐색 성공 시
                nQueen(row + 1); // 다음 depth(행) 탐색
            }
            // 실패 시 형제노드로 이동 (for문 col++)
        }
    }

    private static boolean promising(int depth){ // 좌표 비교
        for (int i=0;i<depth;i++){ // 새로 놓을 퀸(depth)-이미 놓인 퀸(i) 비교
            if (array[depth] == array[i]) return false; // 같은 열
            if (Math.abs(depth-i) == Math.abs(array[depth] - array[i])) return false; // 같은 대각선상
        }

        return true;
    }

}

 

백트래킹 문제를 처음 풀어보는 것이라 헤매다가 백트래킹에 대해 배우고 다른 레퍼런스들을 참고하면서 풀었다. 

 

트리를 떠올리면서 풀 때 각 depth를 행으로, 같은 레벨의 노드들은 열로 치환해서 생각하면 이해가 빠르게 될 것 같아서 좌표 배열의 index는 행, 값은 열로 정했다. 

 

풀면서 아직 재귀함수에 대해 100% 이해 못 한 것을 다시 한번 느낄 수 있었다. 지금은 입력값에 대한 연산 과정을 순차적으로 생각해가며 풀고 있는데 언젠간 더 개념적으로, 추상적으로 이해하면서 풀어야겠지. 그런 김에 다음 번에는 재귀 문제를 풀어야겠다..!

 

 

 

• 참고

https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/