[백준 / 골드4] 9663 N-Queen

문제 보기

사용한 것

• 서로 공격할 수 있는 경우를 제외하기 위한 백트래킹

풀이 방법

• 퀸은 같은 row에 존재할 수 없으므로 queens의 index를 row, value를 column으로
• 백트래킹 조건 : 이전에 배치한 퀸들이 새로 배치할 퀸을 공격할 수 없어야 함

코드

public class Main {

    static int N;
    static int[] queens;
    static int answer = 0;

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

        backtrack(1);

        System.out.println(answer);
    }

    public static void backtrack(int r) {
        if (r == N + 1) {
            answer++;
            return;
        }

        // columns
        for (int i = 1; i <= N; i++) {
            if (queens[r] == 0 && isSafe(r, i)) {
                queens[r] = i;
                backtrack(r + 1);
                queens[r] = 0;
            }
        }
    }

    public static boolean isSafe(int r, int c) {
        // rows
        for (int i = 1; i < r; i++) {
            int opR = i;
            int opC = queens[i];

            if (c == opC || Math.abs(r - opR) == Math.abs(c - opC)) {
                return false;
            }
        }

        return true;
    }
}