[백준] BOJ_9663 JAVA

BOJ_9663 N-Queen

문제

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

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

입력

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

출력

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

예제 입&출력

입 : 4 / 출 : 2
입 : 6 / 출 : 4
입 : 8 / 출 : 92

소스코드

import java.util.Scanner;

public class Main {
    private static int n;
    private static int[] arr;
    private static int cnt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        arr = new int[n]; //arr = 열의 정보

        nQueen(0); //depth = 행의 정보
        System.out.println(cnt);
    }

    private static void nQueen(int depth) {
        if (depth == n) { //행이 n에 다다랐을 때
            cnt++;
            return;
        }

        for (int i = 0; i < n; i++) {
            arr[depth] = i; // depth 행, i열에 퀸이 놓였다!
            if (isPossible(depth)) { // 놓을 수 있는 경우를 확인하자!
                nQueen(depth + 1); // 놓을 수 있다면 다음 행 확인하러!
            }
        }
    }

    private static boolean isPossible(int col) {
        for (int i = 0; i < col; i++) {
            if(arr[col] == arr[i]) return false; //해당 열의 행과 i열의 행이 같으면 x

            if(Math.abs(col - i) == Math.abs(arr[col] - arr[i])) return false; //대각선에 놓여있다면 x
        }
        return true;
    }
}

Comment

• 조건의 중요성을 판단하여 가설해보자
• 위의 소스코드는 depth가 row(행)의 정보라고 생각한 것 같다. 주석을 보면서 생각해보자.
• 참고 블로그