BOJ 9663 N-Queen [Java]

BOJ 9663 N-Queen

1. 문제 링크

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

2. 문제 해설

퀸이 체스판에서 서로 공격할 수 없으려면 3가지 조건을 다 만족해야한다. 같은 행, 같은 열, 대각선 상에 퀸이 존재하면 안된다.
여기서 우리가 퀸을 한 행에는 한개씩만 두기로 해보자. 그렇다면 퀸이 같은 행에 존재하는 경우는 없으므로 조건 중에 1가지는 생각하지 않아도 된다.
1차원 배열을 이용하여서 퀸의 위치를 표현했다. queen[i] = j 라고 하면, i번째 행의 퀸은 j열에 존재한다라는 의미이다.
퀸을 놓는 것은 백트래킹 과정을 이용하여 간단하게 해결가능하다. 23~37줄의 solve 메서드를 살펴보자.
solve 메서드의 매개변수는 r로 현재 행을 의미한다. 그러므로 r == n 이 될 때, solve 메서드를 탈출한다.
r행에 퀸을 i열에 놓았다면 r행의 이전 행에 위치하는 퀸들과 r행 퀸의 위치를 비교하면서 서로 공격할 수 없는지 살펴본다.
공격할 수 없다면 다음 행에도 퀸을 놓는다. (solve 메서드 재귀적으로 호출)

3. 코드 보기

import java.io.*;

public class Main {
    static int n, ans;
    static int[] queen;

    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());
        ans = 0;
        queen = new int[n];

        solve(0);

        bw.write(Integer.toString(ans));
        br.close();
        bw.flush();
        bw.close();
    }

    static void solve(int r) {
        if (r == n) {
            ans++;

            return;
        }

        for (int i = 0; i < n; i++) { // r행의 열들을 다 살펴봄.
            queen[r] = i;

            if (isPossible(r)) {
                solve(r + 1);
            }
        }
    }

    static boolean isPossible(int r) { // r행 이전의 행들에 존재하는 퀸들과 r행의 퀸을 비교하여 가능한지 여부 파악
        for (int i = 0; i < r; i++) {
            if (queen[r] == queen[i] || Math.abs(r - i) == Math.abs(queen[r] - queen[i])) {
                return false;
            }
        }

        return true;
    }
}