[BOJ] 9663번 : N-Queen

접근 방법

체스판의 최대 크기가 15×15이므로 퀸을 놓는 모든 경우의 수는 225 C 15가 됩니다. 225 C 15의 결과는 약 9×10^22이므로 모든 퀸을 놓고 서로 공격 가능한지 검사하는 것으로는 해결할 수 없습니다. 그래서 퀸을 놓을 때마다 이전에 놓은 퀸들과 서로 공격이 가능한지 검사하는 방식으로 문제를 해결해야 합니다. 퀸들이 서로 상하좌우 방향으로 공격이 가능한지 검사를 하는 방법은 서로 같은 행 혹은 같은 열에 있는지 검사를 하면 쉽게 알 수 있습니다. 대각선 방향으로 서로 공격이 가능한지는 아래의 방법으로 검사가 가능합니다.

행 번호와 열 번호를 서로 더했을 경우 우측상단에서 좌측하단으로 향하는 대각선의 방향의 수들이 서로 같음을 볼 수 있습니다.

행 번호에서 열 번호를 뺄 경우 좌측상단에서 우측하단으로 향하는 대각선의 방향의 수들이 서로 같음을 볼 수 있습니다.

위 두가지 방법을 이용하여 서로 퀸들이 대각선 방향으로 공격이 가능한지 검사할 수 있습니다.

코드

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static int[] columns;
    static int count = 0;

    public static void main (String[] args) {
        input();
        func(0);
        System.out.println(count);
    }

    static void input() {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        columns = new int[n];

        scanner.close();
    }

	// rec은 퀸을 놓을 행의 번호
    static void func(int rec) {
        // 모든 퀸을 서로 공격 불가한 위치에 놓았을 경우
        if (rec == n) {
            ++count;
            return;
        }

		// i는 퀸을 놓을 열의 번호
        for (int i = 0; i < n; ++i) {
            boolean placable = true;
            
            // 이전에 놓은 퀸들과 공격 가능한지 검사한다.
            for (int j = 0; j < rec; ++j) {
                // 서로 공격 가능할 경우
                if (attackable(j, columns[j], rec, i)) {
                    placable = false;
                    break;
                }
            }
            
            // rec, i 위치에 놓을 수 있을 경우
            if (placable) {
                columns[rec] = i;
                func(rec + 1); // 다음 행에 대해 
            }
        }
    }

    // 두 위치의 퀸이 서로 공격 가능한지 검사하는 함수
    static boolean attackable(int row1, int col1, int row2, int col2) {
        if (col1 == col2) return true;
        
        // 우측상단에서 좌측하단으로 그은 대각선에 위치했는지
        if (row1 + col1 == row2 + col2) return true;
        
        // 좌측상단에서 우측하단으로 그은 대각선에 위치했는지
        if (row1 - col1 == row2 - col2) return true;

		// 서로 공격 불가
        return false;
    }
}