[백준 JAVA] 9663. N-Queen

문제 링크

---

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

접근 방법

---

한 줄씩 퀸을 배치하며 다음 줄로 이동하는 방식으로 백트래킹을 수행합니다.
같은 열이나 대각선에 퀸이 있는지 확인하여 유망하지 않으면 가지치기를 합니다.

소스 코드

---

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

public class Main {

    static int n, cnt = 0;
    static int[] board;
    static boolean[] isQueen;

    public static boolean checkQueen(int idx) {
        if (isQueen[board[idx]]) {
            return false;
        }

        for (int i = 0; i < idx; i++) {
            if (Math.abs(i - idx) == Math.abs(board[i] - board[idx])) {
                return false;
            }
        }

        return true;
    }

    public static void nQueen(int idx) {
        if (idx == n) {
            ++cnt;
            return;
        }

        for (int i = 0; i < n; i++) {
            board[idx] = i;

            if (checkQueen(idx)) {
                isQueen[i] = true;
                nQueen(idx + 1);
                isQueen[i] = false;
            }
        }
    }

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

        board = new int[n];
        isQueen = new boolean[n];

        nQueen(0);
        System.out.println(cnt);
    }
}

코드 설명

---

board[i]는 i번째 행에 퀸이 놓인 열을 의미합니다.
checkQueen() 함수는 같은 열 혹은 대각선 상에 다른 퀸이 있는지를 검사합니다.
가능한 경우에만 다음 행으로 백트래킹을 진행하며, 마지막 행까지 도달하면 경우의 수를 증가시킵니다.