[백준/Java] 9663: N-Queen

9663번: N-Queen

문제

정수 N이 입력으로 주어질 때, 크기가 N x N인 체스판 위에 퀸 N개를 놓을 수 있는 모든 경우의 수를 출력한다. N-queen 문제는 백트래킹으로 풀 수 있는 유명한 알고리즘 문제 중 하나이다.

 

백트래킹 (Backtracking)

상태공간트리란 문제 해결 과정에서 해를 포함하고 있는 트리이다. 해가 존재한다면 그 해는 반드시 상태공간트리의 어떤 노드에 해당하므로, 이 트리를 체계적으로 탐색하면 언젠가는 해를 구할 수 있다.

 

해를 찾기 위해 상태공간트리를 완전탐색해야만 하는 것은 아니다. 상태공간트리를 깊이우선탐색(DFS)하여 효율적으로 해를 찾아낼 수 있다. 이런 탐색 방법을 되추적 기법(Backtracking)이라고 한다.

DFS로 트리를 탐색해 내려가면서 해를 찾지 못해 막힌다면(조건에 맞지 않는다면) 탐색을 중단하고 이전 단계로 퇴각한다.

 

 

N x N 크기의 체스판에 N개의 퀸을 배치하려고 할 때, 퀸은 아래와 같이 동일한 행, 열, 대각선 상으로 움직일 수 있다.

따라서 모든 퀸은 같은 행, 열, 대각선에 존재하지 않도록 배치되어야 한다.

 

백트래킹 기법으로 문제의 해를 구하기 위해 queens 함수를 재귀함수로 구현한다. 함수의 리턴값은 bool 타입인데, 더 이상 내려갈 수 없다면 false를 리턴한다. queens 함수의 level은 현재 트리의 어떤 노드에 있는지를 나타내며 0부터 시작한다.

promising 함수는 충돌 여부를 검사하는 함수이다. 만약 promising 함수가 false를 리턴한다면 충돌이 있었던 것이므로 이전 단계로 퇴각해야 한다. 함수의 순환호출을 반복하면서 만약 level이 N과 같아진다면(모든 탐색이 끝난 뒤에도 여전히 탐색이 중지되지 않았다면) true를 리턴한다. 이때 cols 배열은 배치된 퀸의 위치를 나타내는 배열이다.

 

소스코드

import java.io.*;
import static java.lang.Math.abs;

public class Main {
    static int[] cols = new int[16];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(queens(0, N));
    }

    public static boolean promising(int level) {
        for (int i=1; i<level; i++) {
            if (cols[i] == cols[level]) // 같은 행, 열에서 충돌
                return false;
            else if (level - i == abs(cols[level] - cols[i])) // 대각선에서 충돌
                return false;
        }
        return true;
    }

    public static int queens(int level, int N) {
        if (!promising(level))
            return 0;
        else if (level == N)
            return 1;
        int cnt = 0;
        for (int i=1; i<= N; i++) {
            cols[level + 1] = i;
            cnt += queens(level + 1, N);
        }
        return cnt;
    }
}