[JAVA] 백준 9663번: N-Queen

백트래킹

 

문제

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

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

입력

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

출력

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

 

 

 

import java.util.Arrays;
import java.util.Scanner;

public class baekjoon9663 {
    static int[] info;
    static int n;
    static int res;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        info = new int[n];
        dfs(0);
        System.out.println(res);
    }

    static void dfs(int index) {
        if (index == n) {
            res++;

            return;
        }
        for (int i = 0; i < n; i++) {
            info[index] = i;
            if (possible(index)) {
                dfs(index + 1);
            }
            // 방문할 수 있는 위치인지 확인 (백트래킹)
            // 가능하면 다음 인덱스로 이동

        }

    }

    static boolean possible(int index) {
        // g
        for (int i = 1; i <= index; i++) {
            if (info[index - i] == info[index] + i || info[index - i] == info[index] - i
                    || info[index - i] == info[index]) {
                return false;
            }
        }
        return true;
        // 이전 열에 대해서만 확인
        // 대각선 또는 가로 행에 방문한 적이 있는지 확인.
        // 방문한 적이 없다면 true를 돌려줌
        // 방문한 적이 있으면 false를 돌려줌
    }
}