[백준] N-Queens Java

문제 링크

1. 문제 설명

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

2. 문제 접근

매우매우 유명한 백트래킹의 대표격 문제입니다. 백트래킹은 브루트 포스 알고리즘과 같이 모든 가능한 경우를 탐색하지만 탐색을 하며 해가 될 수 없는/유망하지 않은 (Unpromising) 분기들을 차단하여 탐색량을 줄이는 알고리즘입니다. 재귀적 방식을 통해 탐색 중 유망하지 않은 조건 분기를 만나면 선택을 철회하여 이전 상태로 돌아가는 방식입니다. 또한 DFS처럼 탐색할 수 있는 최대 깊이의 분기까지 탐색한 후 다음 분기로 넘어갑니다.

N-Queens 문제를 풀기 위해 체스판의 각 열마다 퀸을 배치해 가고 있습니다. 새로운 퀸을 놓을 때 1. 다른 열에 퀸이 놓여 있는 행, 2. 다른 열의 퀸과 대각선상의 행들을 제외하고 가능한 행에 퀸을 배치할 수 있습니다. 퀸을 놓으면 놓을수록 다음 열에 퀸을 놓을 수 있는 행은 줄어들 것이고, 중간에 더 이상 놓을 수 있는 행이 없다면 가장 마지막에 놓은 퀸을 다른 곳에 놓아 보며 탐색하는 식으로 문제를 풀 수 있습니다.

3. 문제 풀이

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

public class Main {
    static int N;
    static int[] board;
    static boolean[] visited;
    static int result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N];
        visited = new boolean[N];
        result = 0;

        nqueen(0);
        System.out.println(result);
    }

    static void nqueen(int depth) {
        if (depth == N) { // 최대 분기에 도달하면(모두 배치) 정답 + 1
            result++;
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                board[depth] = i;

                if (check(depth)) {
                    visited[i] = true;
                    nqueen(depth + 1);
                    visited[i] = false; // 더 이상의 탐색이 불가능하다면 이전 분기로 되돌아감
                }
            }
        }
    }

    static boolean check(int n) { // 같은 행에 있거나 (board[n] == board[i])
        for (int i = 0; i < n; i++) { // 대각선상에 있다면 불가능
            if (board[n] == board[i] || n - i == Math.abs(board[n] - board[i])) {
                return false;
            }
        }
        return true;
    }
}