[백준 9663번] N-Queen / Java

N-Queen

 

Queen은 같은 행, 같은 열, 대각선 양쪽 모두 공격이 가능하다.

즉, 한 행에 Queen 은 하나만 둘 수 있고, 열, 대각선 양쪽 모두 마찬가지라고 할 수 있다.

 

calc(row) : row 행에 Queen 놓는 함수

0 ~ n-1 의 행이 존재한다. 사이에 Queen을 놓았으면 올바르다고 가정한다.

(row, col)로 col은 row행 어디에 Queen을 놓을지 정하는 부분이다.

 

check() : Queen을 (row, col)에 놓고 행, 열, 양쪽 대각선을 탐색해서 Queen의 존재 여부 체크하는 함수

 

시간 복잡도가 각각의 Queen을 놓을때마다 검사하기에, N^N이 된다. (대각선을 검사하지 않았을 경우)

중복 검사를 할 필요가 없도록 대각선을 체크하주는 배열을 추가적으로 이용한다. 그러면 시간 복잡도가 약 O(1)이 된다.

 

check_col[i] : i 열에 Queen이 존재하면 true

check_dig1[i] : / 오른쪽 위 방향 대각선에 Queen이 있는지 (row + col)

check_dig2[i] : \ 왼쪽 위 방향 대각선에 Queen이 있는지 (row - col)

 

재귀함수를 구현할때 중요한점은 모든 처리(ex:true)가 끝난 후 다시 그 전 상태(false)로 되돌려 주어야 한다는 것이다.

 

 

public class Main {
	static int n;
	static boolean[][] a = new boolean[15][15];
	static boolean[] check_col = new boolean[15];
	static boolean[] check_dig1 = new boolean[40];
	static boolean[] check_dig2 = new boolean[40];
	
	static boolean check(int row, int col) {
		
		// 열 check
		if(check_col[col]) {
			return false;
		}
		// 오른쪽 위 대각선 check
		if(check_dig1[row+col]) {
			return false;
		}
		// 왼쪽 위 대각선 check
		if(check_dig2[row-col+n-1]) {
			return false;
		}
		return true;
	}
	
	static int calc(int row) {
		if (row == n) {
			return 1;
		}
		int cnt = 0;
		for(int col = 0; col < n; col ++) {
			if(check(row, col)) {
				check_dig1[row+col] = true;
				check_dig2[row-col+n-1] = true;
				check_col[col] = true;
				a[row][col] = true;
				cnt += calc(row+1);
				
				check_dig1[row+col] = false;
				check_dig2[row-col+n-1] = false;
				check_col[col] = false;
				a[row][col] = false;
			}
		}
		return cnt;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		System.out.println(calc(0));
	}
}