[백준 9663] N-Queen

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

유명한 NQueen 문제입니다.

체스판 모양으로 2차원 배열을 쓰지 않고

1차원 배열을 사용해  배열의 index는 row를, value는 col로 처리하였습니다

 

맨 윗줄의 첫번째칸에 넣고 

이것이 가능한지 검사 후 가능하면

밑에줄 넣고 다시 검사. 반복 후

검사후 이것이 마지막 줄일때 answer를 늘려주는 방식입니다.

 

	public class Q9663 {
	static int[] arr;
	static int answer;
	static int num;
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	num = sc.nextInt();
	arr=new int[num];
	findnumQ(arr, num, 0);
	System.out.println(answer);
	}
	static boolean promising(int[] arr,int num,int row) {
	for(int i=0; i<row; i++) {
	if(arr[row] == arr[i] || row-i == Math.abs(arr[row]-arr[i])) {
	return false;
	}
	}
	return true;
	}
	static void findnumQ(int[] arr,int num,int row) {
	for(int i=0;i<num;i++) {
	arr[row]=i;
	if(promising(arr, num, row)) {
	if(row==num-1) {
	answer++;
	}else {
	findnumQ(arr, num, row+1);
	}
	}
	}
	}
	}

view raw Q9663.java hosted with ❤ by GitHub