P.9663 N-Queen

코드

import java.io.*;

public class P_9663 {

    static int n;
    static int[] board;
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        board = new int[n];

        chess(0);

        bw.write(Integer.toString(cnt));
        bw.flush();
    }

    public static void chess(int queen_n) {
        if (queen_n == n) {
            cnt++;
            return ;
        }

        for (int i = 0; i < n; i++) {
            board[queen_n] = i;
            if (!checkmate(queen_n)) chess(queen_n + 1);
        }
    }

    public static boolean checkmate(int queen_n) {
        for (int i = 0; i < queen_n; i++) {
            if (board[queen_n] == board[i]) return true;
            if (queen_n - i == Math.abs(board[queen_n] - board[i])) return true;
        }
        return false;
    }
}

 코드 설명

백트래킹을 이용한다.

 

퀸은 체스에서 가로 세로, 대각선으로 이동할 수 있는 기물이다.

위와 같은 특성상 한 행에는 퀸이 하나씩만 있을 수 있다.

그렇기 때문에 체스 보드판을 NxN인 2차원 배열이 아니라 크기가 N인 1차원 배열로도 만들 수 있다.

1차원 배열은 각 행에 퀸이 어느 열에 위치하는지를 저장한다.

만약, 첫 번째 행에 퀸의 위치가 첫 번째 열에 위치한다면 board[0] 은 0을 저장하게 된다.

 

그럼 이제 확인해야 할 것은 가로, 세로, 대각선에 위치하는가이다.

1. 가로

퀸을 board 배열에 위치시킬 때부터 한 칸에 하나의 퀸만 들어가므로 가로는 겹칠 수가 없다.

2. 세로

퀸이 세로로 일렬이라고 하면, 배열 상에서 같은 숫자가 들어가게 된다.

그러므로 현재 놓을 퀸의 번호(행 번호)를 담고 있는 queen_n 전까지 board[queen_n]과 같은 값을 가지는 숫자가 있는지 확인한다.

queen_n전까지 확인하는 이유는 백트래킹의 특성 때문이다.

위 코드는 백트래킹을 하다 실패를 하게 되면 놓을 queen_n만 되돌려놓지 board를 초기화시키지 않는다.

그러므로, 배열의 처음부터 끝까지 검사를 하게 되면 이전에 실패한 백트래킹의 결과물까지 조사하는 꼴이 된다.

3. 대각선

퀸은 바로 행의 대각선 뿐만 아니라 N칸의 행에 있는 모든 퀸이 대각선에 존재하면 안된다.

2번 행 퀸이 3번 열에 있을 때, 1번 행 퀸이 2번 열에 있으면 안되는 것과 마찬가지로

4번 행 퀸이 5번 열에 있으면 안된다는 뜻이다.

 

대각선에 대한 힌트는 각 행의 퀸이 어떤 열에 위치하는 가를 통해 얻을 수 있다.

위의 예시에서 봤을 때 2번 행 퀸과 1번 행 퀸은 행이 1차이난다. (2 - 1)

그리고, 2번 행 퀸의 열과 1번 행 퀸의 열은 1차이난다. (3 - 2)

이 차이가 같게 되면 두 퀸은 같은 대각선 상에 위치하는 것이 된다.

 

위 예시의 2번 행 퀸과 4번 행 퀸도 마찬가지다.

2번 행 퀸과 4번 행 퀸은 행이 2차이난다. (abs(2 - 4))

2번 행 퀸의 열 번호와 4번 행 퀸의 열 번호도 2차이난다. (abs(3 - 5))

두 퀸은 대각선상에 위치하며, 위의 식과도 맞아 떨어진다.

즉, 두 퀸의 행 차이 = 두 퀸의 열 차이가 되면 같은 대각선 상에 위치하는 퀸이 된다.

 

위 연산은 절댓값으로 해야 하는데 2번 행 퀸이 5번 열에 있고, 4번 행 퀸이 3번 열에 있을 때 행 차이는 2 - 4로 -2가 되지만 열 차는 5 - 3으로 2가 된다. 

절댓값으로 계산하지 않을 경우 이처럼 대각선 상에 위치한다고 하더라도 판별해내지 못하게 된다.