[Java] 백준9663 N-Queen

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

가로세로대각선으로 움직일 수 있는 막강한 말인 Queen을 서로 공격할 수 없는 위치에 놓는 경우의 수를 구하는 문제.

한줄에 하나의 Queen밖에 못 놓으므로 맵을 다 선언해주지 않아도 됨.

N크기의 배열을 선언한 후 재귀로 경우의 수를 구한다.

조건 1. 같은 열에 있거나

조건 2. 대각선에 위치할 경우를 제외하고 찾는다.

import java.util.Scanner;
public class Problem9663_NQueen {
	
	static int path[] = new int[16];
	static int n;
	static int ans;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		
		for(int i=0; i<n; i++){
			path[0] = i;
			nQueen(i,0);
		}
		System.out.println(ans);
	}
	private static void nQueen(int x, int y) {
		for(int i=0;i<y;i++){
	        if(path[i]==x || Math.abs(x-path[i])==y-i)
	        	 return;
	    }
	    if(y==n-1){
	        ans++;
	        return;
	    }
	    for(int i=0;i<n;i++){
	        path[y+1]=i;
	        nQueen(i,y+1);
	    }
	}
}