백준 9663번 - N-Queen

구현 방법

퀸을 놓는 경우의 수를 구하는 문제이다. 

직접 해보면서 경우의 수를 파악하는 절차지향적인 사고가 필요하고, 가능한 후보군에 대해서만 탐색하면 되므로 가지치기를 동반하는 백트래킹 알고리즘 문제이다.

 

백트래킹 문제이므로 기본적인 틀은 재귀의 형태를 띌 것이고 재귀는 Base Condtion이 있어야 한다. (x, y) 칸을 움직이며서 해당 칸이 유망하다면 재귀를 타고 그렇지 않다면 재귀를 벗어난다.

유망함을 판단하는 것은 (x, y) 좌표에 대해서 행, 열, 대각선에 퀸이 존재하는 지를 확인하면 된다. N * N 에 대해서 퀸의 존재를 확인하는 지는  O(N) 시간 복잡도를 갖는다. 유망함을 판단할 때 모든 칸에 대해서 순회하면서 판단을 하는 것이 아니라 행, 열, 대각선에 대해서 해당 라인이 사용되었는지를 기록하고 있으면 O(1) 시간 복잡도만으로 유망함을 판단할 수 있다.

 

N * N 체스판을 기준으로 
열은 N 크기의 배열

대각선은 N * 2 - 1 크기의 배열이 필요하다.

 

재귀 함수의 파라미터는 행을 가리키고 재귀함수의 반복문의 인덱스 값이 열을 가리킨다고 했을 때

오른쪽 위 - 왼쪽 아래 대각선은 x(행)+ y(열) 의 인덱스를 갖는다.

오른쪽 아래 - 왼쪽 위 대각선은 x(행) - y(열) + N - 1 의 인덱스를 갖는다.

 

코드

package backtracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BJ9663 {
    private static int N;
    private static boolean[] isUsed1;
    private static boolean[] isUsed2;
    private static boolean[] isUsed3;

    private static int result = 0;

    public static void main(String[] args) throws IOException {
        readInput();
        solve();
    }

    private static void readInput()throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        isUsed1 = new boolean[N];
        isUsed2 = new boolean[2 * N - 1];
        isUsed3 = new boolean[2 * N - 1];
    }

    private static void solve(){
        backtracking(0);
        System.out.println(result);
    }

    private static void backtracking(int n){
        if(n == N){
            result += 1;
            return;
        }

        for(int i = 0; i < N; i++){
            if(!isUsed1[i] && !isUsed2[i + n] && !isUsed3[n - i + N - 1]){
                isUsed1[i] = true;
                isUsed2[i + n] = true;
                isUsed3[n - i + N - 1] = true;
                backtracking(n + 1);
                isUsed1[i] = false;
                isUsed2[i + n] = false;
                isUsed3[n - i + N - 1] = false;
            }
        }
    }
}

결과