[BOJ] 9663 N-Queen - JAVA

1. 문제

https://www.acmicpc.net/problem/9663

9663번: N-Queen

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

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

---

2. 풀이

• 한 열에 한 개만 놓을 수 있으므로 1차원 배열로 관리한다. 해당 열에 방문했다면 true, 아니면 false
• 한 대각선에도 한 개만 놓을 수 있으므로 오른쪽, 왼쪽 대각선도 1차원 배열로 관리한다. 번호는 그림과 같은데, 오른쪽 대각선에 N-1을 더한 것은 배열 인덱스 접근 때문이다.
• 0열부터 N-1열까지 방문하면서 이미 해당 열, 대각선에 방문한 적이 있다면 넘어간다.
• 그렇지 않다면 각 배열에 방문체크를 한 뒤 재귀호출한다.
• 재귀호출에 돌아온 뒤 방문체크를 false로 되돌린다.

import java.util.Scanner;

public class BOJ_9663_NQueen {
    static int N, result;
    static boolean[] col, diagonalR, diagonalL;

    public static void main(String[] args) {
        N = new Scanner(System.in).nextInt();
        col = new boolean[N];
        diagonalR = new boolean[2 * N - 1];
        diagonalL = new boolean[2 * N - 1];
        setQueen(0);
        System.out.println(result);

    }

    private static void setQueen(int j) {
        if (j >= N) {
            ++result;
            return;
        }

        for (int i = 0; i < N; i++) {
            if (col[i] || diagonalL[j + i] || diagonalR[j - i + N - 1]) continue;

            col[i] = true;
            diagonalL[j + i] = true;
            diagonalR[j - i + N - 1] = true;

            setQueen(j + 1);

            col[i] = false;
            diagonalL[j + i] = false;
            diagonalR[j - i + N - 1] = false;

        }
    }

}

---

3. 결과

아래는 for문으로 하나하나 대각선을 탐색한 코드다. 대각선도 따로 관리하니 시간이 절반정도 단축되었다.