[백준] 9663 - N-Queen (자바/Java)

문제

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

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

입력

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

출력

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

---

dfs를 활용해서 풀 수 있다는 건 쉽게 파악이 되는데 시간 초과와 메모리 초과때문에 오래 걸린 문제였다.

일단 처음에는 chess 배열에 queen을 하나씩 저장하면서 dfs로 깊이가 N이 될 때까지 검사하려고 하였다.

 

r과 c를 이중 for문을 돌며 모두 검사하다 보니 row=0일 때 검사한 결과를 다시 row=1일 때도 추가하는 문제가 발생하였다.

그래서 dfs 함수에 row를 변수로 넣어주고 검사를 하였는데, 생각해보니 row를 모두 검사할 필요가 없이 row를 1씩 증가하면서 col과 대각선만 비교하면 되는 문제였다.

어차피 하나의 row에는 queen이 하나만 놓일 수 있으니 각 행에서의 col 위치에 따라 배열이 달라지는 것이다.

---

queen배열의 index는 row값을, 각 index의 value들은 queen이 있는 col 값을 의미한다. 

	static void dfs(int row) {
		if (row == N) {
			cnt++;
			return;
		}

		for (int col = 0; col < N; col++) {
			if (check(row, col)) {
				queen[row] = col;
				dfs(row + 1);
				queen[row] = 0;
			}
		}
	}

row가 N이 되면 N-1까지의 queen의 위치를 모두 정한 것이어서 cnt를 1씩 더해주고 종료한다.

check(row, col)이 true라면 해당 위치에 queen이 위치할 수 있는 것이어서 값을 담아주고 row를 1 증가시켜 dfs를 재귀적으로 반복한다.

 

 또 같은 column과 대각선에 queen이 있는지 확인하기 위해 check 함수를 구현하였다.

	static boolean check(int row, int col) {
		for (int r = 0; r < row; r++) {
			if (queen[r] == col)
				return false;
			if (Math.abs(queen[r] - col) == Math.abs(r - row))
				return false;
		}
		return true;

	}

0부터 row-1까지의 col값 중에 현재의 col값과 같은 값이 있다면 false를 return한다.

또한 두 좌표의 col값의 차이와 row값의 차이의 절댓값이 같다면 대각선에 존재하는 것이니 false를 리턴한다.

 

 

 전체 코드

package Gold.g4;

import java.util.Scanner;

public class BOJ_9663_Queen {

	static int[] queen; // index는 row 좌표, col은 index의 값
	static int N;
	static int cnt = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		queen = new int[N];
		dfs(0);
		System.out.println(cnt);

	}

	static void dfs(int row) {
		if (row == N) {
			cnt++;
			return;
		}

		for (int col = 0; col < N; col++) {
			if (check(row, col)) {
				queen[row] = col;
				dfs(row + 1);
				queen[row] = 0;
			}
		}
	}

	static boolean check(int row, int col) {
		for (int r = 0; r < row; r++) {
			if (queen[r] == col)
				return false;
			if (Math.abs(queen[r] - col) == Math.abs(r - row))
				return false;
		}
		return true;

	}
}