[9663 - JAVA] N-Queen

 

문제

 

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

 

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

 

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

풀이

 

문제 풀 때 상하좌우 즉 가로 세로 부분 확인하는 아이디어는 금방 떠올랐지만 대각선 일치 여부를 확인하는 아이디어를 떠올리는데 실패해 검색을 통해 방법을 알아냈다. 

대각선의 겹침 여부를 알아내는 방법으로는 행, 열의 차이 값을 비교해 알 수 있는데

| row_1 - row_2 | == | col_1 - col_2 | 일치한다면 대각선이 겹치는 것이고 아니라면 겹치지 않는다. 해당 공식만 알고 있다면 일반적인 백트레킹 알고리즘을 이용해 풀 수 있다. 

 

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

class Main {
    static int n, count, chessboard[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        chessboard = new int[n];
        
        dfs(0);

        System.out.println(count);
        
    }
    
    static void dfs(int idx) {
        if (idx == n) {
            count++;
            return;
        }

        for (int i = 0; i < n; i++) {
            chessboard[idx] = i;
            if (isCheck(idx)){
                dfs(idx + 1);
            }
        }
    }

    // 상하좌우, 대각선
    static boolean isCheck(int idx) {
        for (int i = 0; i < idx; i++) {
           if (chessboard[idx] == chessboard[i]) {
               return false;
           }
           else if (idx - i == Math.abs(chessboard[idx] - chessboard[i])) {
               return false;
            }
        }

        return true;
    }

}