[백준] N-Queen

참고 : www.acmicpc.net/problem/9663

9663번: N-Queen

 

 - 백트래킹 문제

 - 위치상 불가능한 점을 잡는 방식을 잘 기억할 것.

(신박 y 가 같은 경우, x+y 가 같은 경우, x-y 가 같은 경우는 queen 이 위치할 수 없다)

 

import java.util.Scanner;

public class Solution {
    private static int n;
    private static boolean[] isused1 = new boolean[40]; // y
    private static boolean[] isused2 = new boolean[40]; // x+y
    private static boolean[] isused3 = new boolean[40]; // x-y + n -1
    private static int count = 0;

    // ex n = 4, m = 3
    private static void func(int  cur) {
        if(cur == n) {
            count++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if(isused1[i] || isused2[cur+i] || isused3[cur-i+n-1])
                continue;
            isused1[i] = true;
            isused2[cur+i] = true;
            isused3[cur-i + n -1] = true;
            func(cur+1);
            isused1[i] = false;
            isused2[cur+i] = false;
            isused3[cur-i+n-1] = false;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        func(0);
        System.out.println(count);

    }
}