[백준] N-Queen 9663 - Java

문제

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

9663번: N-Queen

풀이

전체 경우의 수에 대하여 탐색해야 하므로 Back Tracking을 이용하는 문제이다.

 

퀸은 가로, 세로, 대각선으로 이동할 수 있다. 

따라서 퀸 n개는 같은 가로줄, 세로줄, 대각선 줄에 존재하면 안된다.

 

예를 들어보자.

4x4 체스판에 4개의 퀸을 놓는다고 생각하자

(1,1) 과 (2,3)에 퀸을 놓았을 경우 3번째 행에는 퀸이 올수가 없다. 이는 다음의 그림을 통해 확인 할 수 있다.

 

따라서 퀸이 어딨는지 확인할 수 있는 배열 3개가 필요하다.

row 배열 : 세로줄에 대해 퀸이 있을경우 true, 없을경우 false

uppercross : 윗대각선(↗)에 대해 퀸이 있을경우 true, 없을 경우 false

lowercross : 아래대각선(↘)에 대해 퀸이 있을 경우 true, 없을 경우 false

 

uppercross와 lowercross는 index가 다름을 유념해야 한다.

4x4를 다시 생각해보면 uppercross와 lowercross의 배열의 크기는 7이 된다.

이는 대각선끼리 그으면 확인 할 수 있다.

uppercross(↗)의 경우 같은 대각선에 있을 경우 row index와 column index를 더하면 서로 같은 값이 나온다. 이는 아래의 그림에서도 확인 할 수 있다. 따라서, 더하면 같은 값이 나오는 것을 이용하여 index를 설정 하면 된다.

lowercross(↘)의 경우 같은 대각선에 있을 경우 row index와 column index를 빼면 서로 같은 값이 나온다. 따라서, 빼면 같은 값이 나오는 것을 이용하여 index를 설정 하면 된다.

코드

import java.io.*;
import java.util.*;

public class Main {	 
	
	static int n;
	static boolean column[];
	static boolean uppercross[];
	static boolean lowercross[];
	static int result = 0;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				
		n = Integer.parseInt(br.readLine());

		column = new boolean[n];
		uppercross = new boolean[2*n-1];
		lowercross = new boolean[2*n-1];
		
		back(0);
		
		System.out.print(result);
	}
	
	static void back(int cnt) {
		if(cnt == n) {
			result++;
			return;
		}
		
		for(int i=0;i<n;i++) {
			if(!column[i] && !uppercross[cnt + i] && !lowercross[cnt - i + n - 1]) {
				column[i] = true;
				uppercross[cnt+i] = true;
				lowercross[cnt - i + n - 1] = true;
				back(cnt+1);
				column[i] = false;
				uppercross[cnt+i] = false;
				lowercross[cnt - i + n - 1] = false;
			}
			
		}
	}
	
}