[BAEKJOON 백준] 9663 N-Queen (JAVA)

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

9663번: N-Queen

 

문제

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

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

입력

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

출력

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

 

 

재귀와 DP를 섞어서 문제를 해결했습니다.

재귀로 하나의 DP가 만들어질 때마다 결과값이 1씩 올라가도록 했습니다.

그리고 check를 만들어서 퀸이 겹치게 올라가지 않도록 가지치기를 해서 결과가 나오도록 작성했습니다.

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

public class Main {
	private static int N;
	private static int result;
	private static int[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		find(0);
		System.out.println(result);
	}

	private static void find(int cnt) {	//재귀 하나 만들어질 때마다 result를 하나씩 올려줌
		if (cnt == N) {
			result++;
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			arr[cnt] = i;
			if (check(cnt)) {
				find(cnt + 1);
			}
		}
	}

	private static boolean check(int col) {		//같은 열이나 대각선에 있을 경우 False
		for (int i = 0; i < col; i++) {
			if (arr[col] == arr[i]) {
				return false;
			} else if (Math.abs(col - i) == Math.abs(arr[col] - arr[i])) {
				return false;
			}
		}
		return true;

	}
}