[백준] 9663 - N-Queen | Java

📌 문제 정보

[9663: N-Queen]

---

💡 접근 방식

퀸은 수평, 수직, 대각선으로 이동 가능하다.
N x N 체스판에 퀸을 N개를 두려면 한 행에 하나씩은 들어가야 한다.

한 행마다 하나의 퀸을 놓는 방식으로 진행하면 수평 체크는 따로 진행할 것 없이 수직과 대각선만 확인하면 된다.

수직은 간단히 boolean[] col로 확인한다.

대각선은 boolean[] rightDown과 boolean[] leftDown으로 확인했다.

leftDown(↙) 대각선은 각 row와 col의 합이 동일하다.

4 x 4 배열을 예시로 (0,3) → (1,2) → (2,1) → (3,0) 대각선이 있을 때
각 row+col은 3으로 동일하다.

rightDown(↘) 대각선은 각 row와 col의 차가 동일하다.

마찬가지로 4 x 4 배열에서 (0,0) → (1,1) → (2,2) → (3,3) 대각선이 있을 때
각 row-col은 0으로 동일한 것을 알 수 있다.

그래서 2차원 배열을 두어서 좌표를 계산할 것 없이 각 대각선이 가능한 범위를 인덱스로 체크하면 된다!

---

✅ 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static int n;
    static int cnt;
    static boolean[] col;
    static boolean[] leftDown;
    static boolean[] rightDown;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        col = new boolean[n];
        leftDown = new boolean[2 * n - 1]; // (row + col)
        rightDown = new boolean[2 * n - 1]; // (row - col + n - 1)

        queen(0);

        System.out.println(cnt);

    }

    public static void queen(int row) {

        if (row == n) {
            cnt++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (col[i] || rightDown[row + i] || leftDown[row - i + n - 1]) {
                continue;
            }

            col[i] = true;
            rightDown[row + i] = true;
            leftDown[row - i + n - 1] = true;

            queen(row + 1);

            col[i] = false;
            rightDown[row + i] = false;
            leftDown[row - i + n - 1] = false;

        }

    }

}

---

🧠 배운 점 & 회고

백트래킹 자체는 익숙했는데, 대각선을 어떻게 처리하면 좋을지 고민했다.
최근에 2차원 배열을 다루는 문제만 풀었어서 그런지 처음엔 이 문제도 2차원 배열로 접근했었다. 근데 풀면서 생각해보니 어차피 퀸은 한 줄에 하나씩만 들어가니까.. 굳이 2차원 배열을 둘 필요가 없다는 것을 깨달았다!

---

🧾 결과