[백준알고리즘] 9663번: N-Queen -Java

[백준알고리즘] 9663번: N-Queen -Java

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

9663번: N-Queen

드디어! BackTracking 분류에서 대표적인 백트래킹 문제인 N-Queen문제가 나왔다.

 

체스판에서 퀸은 가로, 세로, 대각선 방향으로 모두 길이 제한 없이 이동이 가능하다. 즉 각자의 가로, 세로, 대각선에 다른 퀸이 놓이지 않게 N X N 행렬 위에 N개의 퀸을 올리면 되는 문제이다. 

 

이 문제를 처음에 주어진 것처럼 NxN행렬로 만들어서 구하다가 메모리 초과 나는 것을 보고 그제야 메모리 제한을 확인했다.... 15x15 행렬을 몇 개를 만들었던지... 처음부터 확인할걸... 그래서 푸는 방법을 생각하다가 Nx1 행 행렬로 구할 수 있음을 찾았다.

 

 

아래와 같이 크기가 15이며 -1로 초기화된 정수 배열을 만들었다. 15x15행렬의 i행 j열을 가리키기 위해 배열의 0~14번 인덱스가 각 행을 가리키며, 그 안의 값이 열을 가리키도록 생각했다. 즉, matrix[3][5]에 퀸을 놓았다는 것은 array[3] = 5로 표현을 한다는 것이다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1

 

여기서 규칙을 생각해봐야 한다. 우선 퀸은 가로와 세로 모두 갈 수 있기 때문에 (i, j)에 퀸을 놓게 되면 i행과 j열에는 더 이상 퀸을 놓지 못하게 된다. 따라서 0번 행부터 하나의 행씩 순서대로 이전의 행들에 놓인 j(열) 값과 겹치지 않게 위치시키면 된다.

여기서 추가적으로 대각선을 고려하면 된다. (i, j)의 위치한 퀸이 대각선으로 이동가능한 위치를 (p, q)라고 했을 때 |p-i| = |q-j|가 된다. 즉 이동한 위치와 원래 위치의 행의 차이의 절댓값과 열의 차이의 절댓값이 일치한다는 것이다.

 

아래의 표를 다시 확인하도록 하자.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
3	6	?	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1

 

주어진 체스판의 크기가 15x15일때 위의 표에서의 상황은 (0, 3)에 퀸을 놓고, (1, 6)에 퀸을 놓은 상태이다. (2, ?)에 놓으려고 할 때 가능한 위치를 찾는 것이다. 2행에서는 우선 0행과 1행에서 퀸이 놓인 3열과 6열에는 놓지 못한다. 따라서 우선 가능한 열의 집합은 {0, 1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14}이다.

이제 대각선을 생각해보도록 하자. 2행과 1행의 차이는 1이다. 그 말은 1행의 열과 차이가 1인 열은 2행에서 놓지 못한다. 따라서 (2, 6-1=5), (2, 6+1=7)에는 퀸을 놓지 못한다. 마찬가지로 2행은 0행과 차이가 2가 나기 때문에 0행의 열이 3이므로 (2, 3-2=1), (2, 3+2=5)에도 두지 못한다. 즉 가능한 열의 집합은 {0, 2, 4, 8, 9, 10, 11, 12, 13, 14}이 되는 것이다.

 

방금한 불가능한 위치는 더 이상 깊이 내려가지 않는 이 부분이 Prunning이며 DFS와 Backtracking 의 차이점이라고 볼 수 있다.

 

이 방법을 계속해서 반복해서 14번 행까지 모두 가능한 경우에 total count를 +1 시켜주면서 세주면 된다. 

 

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

public class Main {
	
	private static int N;
	static int total;
	
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int [] visit = new int [15];
		Arrays.fill(visit, -1);
		
		try {
			N = Integer.parseInt(br.readLine());
			br.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		solve(visit, 0);

		try {
			bw.write(String.valueOf(total));
			bw.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	private static void solve(int [] visit, int cnt) {
		if(cnt == N) {
			total++;
			return;
		}
		
		boolean [] available = new boolean [15];

		// check
		for(int i = 0; i < cnt; i++) {
			int t = visit[i];
			available[t] = true;
			if(t + cnt - i < N) available[t + cnt - i] = true;
			if(t - cnt + i >= 0) available[t - cnt + i] = true;
		}
		
		// not visited
		for(int i = 0; i < N; i++) {
			if( !available[i] ) {
				visit[cnt] = i;
				solve(visit, cnt + 1);
				visit[cnt] = -1;
			}
		}
	}

}

 

오랜만에 자바를 만졌더니 어질어질하다...

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다