[KOITP] N-Queen

출처 : http://koitp.org/problem/NQUEEN/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	256 MB	949	483 (51%)	378

문제

N-Queen문제는 유명한 문제이다. 이는 N × N인 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하시오.

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 12)

출력

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

힌트

예제 입력

4

예제 출력

2

< Comment >

 BackTracking 에 대해서는 그다지 어렵다는 인상이 아니어서 대충 가능할 거라고 여겼는데, 다시 한 번 봐야 할 것 같습니다. 생각보다 한참 고민하면서 풀었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class NQueen {
	
	public static int N = 0;		// [ 1, 12 ]
	
	public static int answer = 0;
	
	public static boolean isPossible (int[] col, int row) {
		
		for (int i  = 0 ; i < row ; i++) {
			
			if (col[i] == col[row]) {
				return false;
			} else if (Math.abs(col[i] - col[row]) == Math.abs(i - row)) {
				return false;
			}		
		}
		
		return true;
	}
	
	public static void f(int[] col, int row) {
		
		if (row == N) {
			answer++;
			return;
		}
		
		for (int i = 0 ; i < N ; i++) {
			
			col[row] = i;		// 일단 넣어두고
			if(isPossible(col, row)) {
				f(col, row + 1);
			}
		}
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		int[] col = new int[N];			// (index, 값) 에 퀸이 존재
		
		f(col, 0);
		
		bw.write("" + answer);
		bw.flush();
		bw.close();
	}
}