[백준 9663] N-Queen(Java)

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

9663번: N-Queen

문제

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

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

입력

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

출력

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

예제 입력 1

8

예제 출력 1

92

풀이 설명

1. 전체 map의 각 행마다 어느 열에 퀸을 놓았는지 저장하는 배열 arr을 선언한다.

2. map을 탐색하며 퀸을 놓는 함수 dfs를 선언하고, 현재 행의 위치 current를 매개변수로 넘긴다. 처음 시작은 0이다.

  2-1. 0~N-1 열까지 탐색하며 해당 칸이 check함수에 부합하면(같은 열이나 대각선에 있지 않다면

        (어차피 행은 dfs가 호출될 때마다 1씩 늘어나므로 같지 않다.) 그 칸에 퀸을 놓는다.

  2-2. dfs에 현재 행의 위치 +1을 넘겨 재귀호출한다.

  2-3. 현재 위치가 N이 된다면 퀸을 모두 배치했으므로, 전체 count를 1 올린다.

Java 코드

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

public class Main {
	
	static int N;
	static int[] arr;
	static int count;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N]; //각 행마다 퀸을 놓은 열 인덱스 저장
		
		dfs(0);
		System.out.println(count);
	}

	public static void dfs(int current) {
		if(current == N) {
			count++;
			return;
		}
		for(int i=0; i<N; i++) {
			if(check(current, i)) {
				arr[current] = i;
				dfs(current+1);
			}
		}
	}
	
	public static boolean check(int current, int idx) {
		for(int i=0; i<current; i++) {
			if(arr[i] == idx) //같은 열에 있거나
				return false;
			if(Math.abs(i - current) == Math.abs(arr[i] - idx)) //대각선에 있으면
				return false;
		}
		return true;
	}
}