[백준 / BOJ] 9663번 : N-Queen - JAVA

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

9663번: N-Queen

순열 Permutation + 2차원 배열

내가 이 문제를 푼 건 순열과 2차원 배열을 사용한 것인데, 다른 사람의 제출을 확인했을 때 비트마스킹으로 깔끔하게 푼 풀이가 있었다. 일단 내가 푼 방법을 적고, 비트마스킹으로 푸는 방법을 소개하려고 한다.

 

일단 제한시간이 10초나 되기 때문에 순열로 풀어도 될 것이라 판단했다. 한 행 당 한 번의 선택을 한다해도 안되는 부분을 체크한다면 15!이나 걸릴 리 없기 때문이다.

 

Queen은 상하좌우, 그리고 대각선으로 움직일 수 있다. 움직이는 칸수의 제한은 없다. 따라서 순열에서 i를 선택한 후 체크를 해줄 때, 현재 이후(cnt 행 이후)에는 i열과, 대각선 열을 선택할 수 없도록 방문 체크해주었다.

for (int j = cnt; j < N; j++) {
    col[j][i]++;
    if(i + j - cnt < N) col[j][i + (j - cnt)]++;
    if(i - (j - cnt) >= 0) col[j][i - (j - cnt)]++;
}

이 때 boolean이 아니라 int 배열로 해서 수를 하나씩 늘린 것은 단순 true, false로 체크하는 경우, 함수 호출 후 이전 상태로 초기화할 때 다시 false로 돌려도 되는지 판단하기 어렵기 때문이다. 현재 행 때문에 true로 바뀐 건지, 혹은 이전에 다른 행을 체크할 때 이미 true로 바뀌어 있었는지 알 수 없다. 따라서 1씩 숫자를 늘려가고, 0일 때에만 선택할 수 있도록 했다.

 

임시 boolean 2차원 배열을 매번 생성해서 col 배열을 복사하고 함수 호출 시 넣어주면 안되는가? 하는 의문이 들 수도 있는데, 매번 임시 배열을 만들어 제출한 코드는 메모리 초과가 나왔다.

 

순열 + 2차원 배열 전체 코드

// 시간 : 1784ms
// 메모리 : 13088KB
public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		count = 0;
		n_queen(0, new int[N], new int[N][N]);
		System.out.println(count);
	}

	static int count;
	private static void n_queen(int cnt, int[] line, int[][] col) {

		int N = col.length;

		if(cnt == N) {
			count++;
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if(col[cnt][i] > 0) continue;
			
			line[cnt] = i;
			for (int j = cnt; j < N; j++) {
				col[j][i]++;
				if(i + j - cnt < N) col[j][i + (j - cnt)]++;
				if(i - (j - cnt) >= 0) col[j][i - (j - cnt)]++;
			}
			n_queen(cnt + 1, line, col);
			for (int j = cnt; j < N; j++) {
				col[j][i]--;
				if(i + j - cnt < N) col[j][i + (j - cnt)]--;
				if(i - (j - cnt) >= 0) col[j][i - (j - cnt)]--;
			}
		}
	}

}

 

 

순열 Permutation + 비트 마스킹 Bitmasking

사실 비트마스킹은 boolean 배열을 대체할 수 있다. 하지만 단순히 boolean 배열을 대체하는 방식으로 진행한다면 앞서 언급했던 "언제부터 해당 열을 선택할 수 없게 됐는가" 하는 문제가 남는다. 비트마스킹은 기다, 아니다 외의 다른 정보는 넣을 수 없기 때문이다.

 

이 부분은 다른 사람의 풀이를 참고했다. (https://www.acmicpc.net/source/65157114)

 

우선, N의 크기에 따라 전체 열을 모두 선택한 경우의 값 full을 만들었다. 0부터 N-1번째 bit가 모두 1인 수이기 때문에 ~(1 << N)과 동일하다.

full = ~(1 << N);

그리고 순열 함수에는 2차원 배열이 아니라, left, center, right가 들어간다. 이는 각각 이미 선택된 열들의 왼쪽 대각선 방향으로 불가능한 열,  이미 선택된 열, 이미 선택된 열들의 오른쪽 대각선 방향으로 불가능한 열을 의미한다. 만일 이 세 가지를 모두 AND 연산했을 때 full과 같다면, 모든 열이 불가능한 것이고 그대로 리턴한다.

int all = (left | center | right);
if(all == full) return;

 

이후에는 순열과 같이 0부터 N - 1까지의 열을 탐색하며 left, center, right에 포함되지 않은 bit를 찾는다.

for (int i = 0; i < N; i++) {
    int col = 1 << i;
    if((all & col) > 0) continue;
    n_queen(cnt + 1, left | col, center | col, right | col);
}

그런데 여기에서 의문이 생길 것이다. 왜 left, center, right 모두에 col을 OR 연산할까? left와 right는 한 칸씩 밀어줘야 하는 것 아닐까?

 

그럴 수도 있지만, 대각선의 특징을 생각해보면 현재 열을 OR 해주고, 다음 함수 호출 시에 한 칸씩 밀어주는 것이 이해하기 편하다. 대각선은 기준점에서 행과 열이 동일한 수만큼 차이가 나는 곳이다. 다음 함수에서는 현재보다 1칸 아래 행을 확인하게 되고, 이는 그 전의 left와 right를 또 한 칸 밀어서 생각해야 한다는 뜻이다.

예를 들어 그림의 1번째 행의 left를 생각해보자. 0번째 행의 왼쪽 대각선 방향과, 1번째 행에서 선택된 자리이다.

이 left를 가지고 그 다음 함수(다음 행을 선택하기 위한)로 넘어간다. 이 때의 모양은 다음처럼 변해야 한다. 

한 칸 내려왔으니, 한 칸 왼쪽으로 밀려나야 하는 것이다. all 변수를 초기화해주기 전, left를 왼쪽으로 한 번 밀어주면 같은 모양을 확인할 수 있다. 이후에도 한 칸 내려갈 때마다 계속 옆으로 한 번씩 밀어주면 된다.

left <<= 1;

 

순열 + 비트마스킹 전체 코드

public class Main {

	static int N;
	static int full;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		full = ~(1 << N);
		
		count = 0;
		n_queen(0, 0, 0, 0);
		System.out.println(count);
	}

	static int count;
	private static void n_queen(int cnt, int left, int center, int right) {

		
		if(cnt == N) {
			count++;
			return;
		}
		
		left <<= 1;
		right >>= 1;
		int all = (left | center | right);
		if(all == full) return;
		
		for (int i = 0; i < N; i++) {
			int col = 1 << i;
			if((all & col) > 0) continue;
			n_queen(cnt + 1, left | col, center | col, right | col);
		}
		
		return;
	}

}