[Java] 9663. N-Queen

www.acmicpc.net/problem/9663

9663번: N-Queen

문제

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

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

입력

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

출력

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

---

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

public class BOJ_9663 {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static int N, map[][], count;

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(in.readLine());
		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			map[0][i] = 1;
			DFS(0, i, 1); // row, col, 갯수
			map[0][i] = 0;
		}
		System.out.println(count);
	}

	private static void DFS(int a, int b, int cnt) {
		if (!checkAv(a, b))
			return;
		if (cnt == N) {
			count++;
			return;
		}
		for (int i = 0; i < N; i++) {
			map[a + 1][i] = 1;
			DFS(a + 1, i, cnt + 1);
			map[a + 1][i] = 0;
		}

	}

	private static boolean checkAv(int a, int b) {
		if (!checkCol(a, b))
			return false;
		if (!checkCross(a, b))
			return false;
		return true;
	}

	private static boolean checkCross(int a, int b) {

		int x = a, y = b;
		while (x > 0 && y > 0) {
			if (map[--x][--y] == 1)
				return false;
		}
		x = a;
		y = b;
		while (x < N - 1 && y < N - 1) {
			if (map[++x][++y] == 1)
				return false;
		}
		x = a;
		y = b;
		while (x > 0 && y < N - 1) {
			if (map[--x][++y] == 1)
				return false;
		}
		x = a;
		y = b;
		while (x < N - 1 && y > 0) {
			if (map[++x][--y] == 1)
				return false;
		}

		return true;
	}

	private static boolean checkCol(int a, int b) {
		int tmp = a;
		while (tmp > 0) {
			if (map[--tmp][b] == 1)
				return false;
		}
		tmp = a;
		while (tmp < N - 1) {
			if (map[++tmp][b] == 1)
				return false;
		}
		return true;
	}

}

 

위와 같이 DFS를 이용해서 탐색을 진행했다. 또한 2차원 배열을 만들고 직접 찍어가면서 탐색을 진행했더니 9초가까이 시간이 걸렸다. 그래서 다른 방법을 찾아 보고, 직접 2차원배열을 사용하지않아도 됨을 알게 되었다.

그래서 수정된 코드는 다음과 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static int N, map[], count;

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(in.readLine());
		map = new int[N+1];
		setQueen(0);
		System.out.println(count);
		
	}
	
	static void setQueen(int rowNum) {
		if(!isAvail(rowNum)) {
			return;
		}
		if(rowNum == N) {
			count++;
			return;
		}
		for (int i = 1; i <= N; i++) {
			map[rowNum+1] = i;
			setQueen(rowNum+1);
		}
	}

	private static boolean isAvail(int no) {
		for (int i = 1; i < no; i++) {
			if(map[no] == map[i] || Math.abs(map[no]-map[i]) == Math.abs(no - i)) {
				return false;
			}
		}
		return true;
	}
}