백준 9663 N-Queen Java

백트래킹 문제에 대명사라고 할 수 있는 N-Queen 문제이다.

나는 백트래킹이 아직 어렵기 때문에 여러 가지 버전의 풀잇법을 봤었는데

이해하기 어려운 버전이 태반이였다.

 

어차피 어려운 거 가장 빠른 걸로 완벽히 이해해보자 하고 

내가 본 것들 중에 가장 빠른 것을 테스트해본 결과

백준 님의 풀이가 가장 빨랐다.

그래서 백준님의 풀잇법으로 정리해보려고 한다.

 

문제 설명을 간단히 하자면 입력받은 N*N의 체스판에서

N개의 퀸이 서로 공격하지 않게 놓을 수 있는 경우의 수를 출력하는 문제이다.

다 알겠지만 체스에서 퀸은 위의 그림처럼 상하좌우, 양쪽 대각선까지 공격할 수 있는 역할이다.

그림에서도  알 수 있듯이 N이 3인 경우까지는 절대 N개의 퀸을 서로 공격하지 않게 놓을 수 없다.

 

그렇다면 N이 4인 경우는 어떨까.

	Q
			Q
Q
		Q

 

		Q
Q
			Q
	Q

위의 표들처럼 2개의 경우가 나올 수 있다.

이런 식으로 N*N의 판에서 N개의 퀸을 서로 공격하지 않게 놓는 경우의 수를 출력하는 것이 문제이다.

 

우선 퀸이 공격하지 않게 놓으려면 확인해야 할 것은

1. 같은 열에 퀸이 있는지

2. 같은 행에 퀸이 있는지

3. 왼쪽 대각선에 퀸이 있는지

4. 오른쪽 대각선에 퀸이 있는지

 

이 4가지를 확인해야 한다.

 

같은 행, 같은 열에는 퀸이 절대 올 수 없다는 점을 이용해서

행을 기준으로 증가시키면서 열을 하나씩 가보며 재귀 호출을 수행한다.

해당 열에 퀸을 놓을 수 있다면 바로 다음 행으로 넘어간다.

이러한 방식을 생각해보면 같은 행 같은 열에는 절대 퀸이 올 수가 없다.

그렇기 때문에 1, 2번 -> 같은 행, 같은 열은 검사할 필요가 없고

3, 4번 왼쪽 대각선, 오른쪽 대각선만 검사해보면 된다.

 

순차적으로 탐색하며 행을 증가시키기 때문에

모든 대각선, 모든 열을 확인하지 않고

바로 위 행의 왼쪽 위 대각선, 오른쪽위 대각선만 확인하면 된다.

	체크		체크
		현 위치

그렇기 때문에 1차원 배열로도 확인이 가능하다.

boolean형 1차원 배열을 3개 만들어서 확인한다.

방문 여부 배열

왼쪽위 대각선 검사 배열

오른쪽 위 대각선 검사 배열

 

방문 여부는 checkCol[col]

현재 열의 위치가 true인지 확인해보면 되고

 

오른쪽 위 대각선의 경우

그림을 참고해서 봤을 때

오른쪽 대각선들은 전부 row+col을 하면 같은 값을 가진다.

오른쪽 대각선 검사 배열[row+col]가 true인지 확인하면 된다.

 

왼쪽 대각선을 검사할 때도 마찬가지이다.

이때는 row-col을 하면 같은 값을 가진다. 하지만

row - col을하면 음수가 나올 수 있기 때문에 n을 더해서 사용한다.

왼쪽 대각선 검사 배열[row-col+n]이 true인지 확인하면 된다.

 

이런 식으로 짜면 check메소드가 O(1)이기 때문에

2차원 배열로 일일이 검사하면서 백트래킹하는 알고리즘보다

훨씬 빠르게 구현할 수 있다.

check가 O(n)인 일일이 검사하는 코드는 O(n^n^n)이고

check가 O(1)인 이 코드는 O(n^n)의 시간 복잡도를 갖게 된다.

 

package baekjoon.exhaustive_search;
 
import java.util.Scanner;
 
 
public class Q9663 {
    static boolean [] checkCol = new boolean[15];
//row+col , row-col+n -> 최대 30
    static boolean [] checkRightDig = new boolean[31];
    static boolean [] checkLeftDig = new boolean[31];
    static int n;
    
    public static boolean check(int row, int col) {
        if(checkCol[col]) { 
            return false;
        }
        if(checkRightDig[row+col]) {
            return false;
        }
        if(checkLeftDig[row-col+n]) {
            return false;
        }
        return true;
    }
    
    public static int calc(int row) {
        if(row == n) {
            return 1;
        }
        
        int cnt = 0;
        for(int col=0; col<n; col++) {
            if(check(row, col)) {
                checkCol[col] = true;
                checkRightDig[row+col] = true;
                checkLeftDig[row-col+n] = true;
                cnt += calc(row+1);
                checkCol[col] = false;
                checkRightDig[row+col] = false;
                checkLeftDig[row-col+n] = false;
            }
        }
        return cnt;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt(); 
        System.out.println(calc(0));
    }
}