[백준]9663번 N-Queen(java)

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

9663번: N-Queen

백준 9663번 N-Queen 문제 링크입니다.

 

핵심

N*N크기의 체스판에 N개의 퀸을 놓는다. 퀸은 일직선, 대각선으로 쭉 움직일 수 있다. 즉 각각의 퀸이 일직선과 대각선에 위치하면 안 된다. 1차원 배열을 사용하여, 각 배열의 index를 열, 값을 행으로 본다.

정답 코드

import java.util.Scanner;
public class Main {
    public static int[] arr;
    public static int N;
    public static int count = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        arr = new int[N];
        nQueen(0);
        System.out.println(count);
    }
    public static void nQueen(int depth) {
        if (depth == N) {
            count++;
            return;
        }
        for (int i = 0; i < N; i++) {
            arr[depth] = i;
            if (Possibility(depth)) {
                nQueen(depth + 1);
            }
        }
    }
    public static boolean Possibility(int col) {
        for (int i = 0; i < col; i++) {
            if (arr[col] == arr[i]) return false;
            else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) return false;
        }
        return true;
    }
}

 

해설

메인 메서드는 N의 값을 받는다. 

nQueen을 보면, depth==N일 때  return 하는데, 이는 모든 퀸을 체스판 위에 올려두었다는 뜻이다. 

따라서 count를 1 올린다.

possibility를 보면 해당 열의 행과 i열의 행이 일치할 경우에는 퀸을 놓을 수 없기 때문에, false를 반환한다.열의 차와 행의 차가 같으면 대각선에 위치한 것이므로 이 또한, false를 반환한다.위의 사항에 해당하지 않으면 퀸을 둘 수 있으므로 true를 반환한다.true가 반환되면, nQueen을 depth+1 한 상태로 재귀 호출한다.