[Java] 백준 9663번 : N-Queen

문제

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

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

입력

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

출력

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

예제 입력 1

8

예제 출력 1

92

 

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int N, cnt=0;
	private static int []choosed;
	public static void main(String[] args) throws NumberFormatException, IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		choosed=new int[N+1];
		
		nQueen(1);
		System.out.println(cnt);
	}

	private static void nQueen(int r) {	// r행에 놓을 수 있는 퀸의 열의 위치 찾기
		if(r>N) {
			cnt++;
			return;
		}
		
		for(int i=1;i<=N;i++) {
			choosed[r]=i;	// r행의 i열에 퀸을 놓음
			if(check(r)) nQueen(r+1);	// 퀸을 놓을 수 있으면 다음 행으로 이동
		}
	}
	
	private static boolean check(int r) {
		for(int i=1;i<r;i++) {
			if(choosed[i]==choosed[r]) return false;	// 앞서 배치한 퀸과 같은 행 불가능
			if(Math.abs(choosed[r]-choosed[i])==Math.abs(r-i)) return false;	// 앞서 배치한 퀸과 같은 대각선 불가능
		}
		return true;
	}
}

대표적인 백트래킹 문제였습니다.