[백준 - 9663] N-Queen - Java

문제 설명

 

9663번: N-Queen

 

접근 방법

해당 문제에서는 n * n 체스판에서 n개의 퀸이 서로를 공격할 수 없도록 배치할 수 있는 경우의 수를 요구하고 있습니다.

 

직관적으로 n개의 퀸을 해당 체스판에 배칠할 수 있는 모든 경우의 수를 구하여 퀸들이 서로 공격하는 여부를 점검하고자하면 압도적인 시간초과가 발생합니다. 왜냐하면 n은 최대 15로, 15개의 퀸을 225칸의 배치할 수 있는 경우의 수가 엄청날 뿐만 아니라, 퀸 서로간 공격 유무를 점검하는 작업은 시간 복잡도 성능이 매우 떨어지기 때문입니다.

 

이때, 퀸을 2차원 배열에 일일이 배치하는 것이 아니라 1차원 배열로 생각하는 방식을 떠올릴 수 있습니다. 1차원 배열로 둘 수 있는 이유는 퀸은 같은 행열간에 존재하게 되면 서로 공격할 수 있게 되므로 애초에 경우의 수에 있어 배제 대상이기 때문입니다. 아울러 퀸들은 같은 행열은 아니어도 대각선 상에 같이 놓이게 되도 서로 공격할 수 있으므로 이 또한 배제 대상입니다.

 

 

전체 소스 코드

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

class Main {

    static int n, result = 0;
    static int[] queens;

    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];
        select(0);

        System.out.println(result);
    }

    private static void select(int countOfSelect) {
        if (countOfSelect == n) {
            result++;
            return;
        }

        for (int i = 0; i < n; i++) {
            queens[countOfSelect] = i;

            if (verify(countOfSelect)) {
                select(countOfSelect + 1);
            }
        }
    }

    private static boolean verify(int i) {
        for (int j = 0; j < i; j++) {
            if (queens[i] == queens[j] || Math.abs(queens[i] - queens[j]) == i - j) {
                return false;
            }
        }

        return true;
    }
}

 

참고자료

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