[백준/java] 9663번: N-Queen - 백트래킹(Back-Tracking) 사용

문제

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

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

입력

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

출력

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

 

※ 풀이 생각해보기

(1) Queen은 한 행에는 같이 있지 않음을 생각해서 해당 행에 대한 조사는 이루어지지 않음

(2) 같은 열에 있는지에 대한 조사 chk1

(3) 대각선 방향 ↙ x, y 합에 대한 조사 chk2

(4) 대각선 방향 ↘ x-y + n-1에 대한 조사 chk3

 

 

package backTracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class NQueen {
	static int N, cnt = 0;
	static boolean[] chk1, chk2, chk3;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		chk1 = new boolean[N];
		chk2 = new boolean[N*2];
		chk3 = new boolean[N*2];
		
		find(0);
		System.out.println(cnt);
	}
	
	public static void find(int k) {
		if(k == N) {
			cnt++;
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if(chk1[i] || chk2[i+k] || chk3[k-i + N-1]) continue;
			chk1[i] = true;
			chk2[i+k] = true;
			chk3[k-i + N-1] = true;
			find(k+1);
			chk1[i] = false;
			chk2[i+k] = false;
			chk3[k-i + N-1] = false;
		}
	}
}