[BOJ]9663号:N-Queen

方法

コード#コード#

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;
    }
}