[Algorithm] 백준 9663 N-Queen

문제

N-Queen 문제는 N*N 체스판에 N개의 퀸을 서로 공격할 수 없게 놓는 문제이다. 퀸은 가로, 세로, 대각선으로 이동할 수 있기 때문에 퀸이 서로 공격할 수 없게 놓으려면 퀸이 서로 같은 행, 같은 열, 같은
대각선에 놓이면 안된다. N이 주어졌을 때, N-Queen 문제의 해의 개수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 N-Queen 문제의 해의 개수를 출력한다.

예제 입력 1

8

예제 출력 1

92

문제를 풀기 위한 아이디어

먼저 브루트 포스로 모든 경우의 수를 생각해봐야 하는 문제이다.

여기서 백트래킹 기법을 사용하여 풀 수 있다.

백트래킹 기법은 DFS를 사용하여 풀 수 있는 문제이다.

DFS를 사용하여 풀 때, 가지치기를 해주어야 한다.

가지치기를 해주는 이유는 불필요한 경우의 수를 제거하기 위해서이다.

굳이 퀸이 퀸을 공격 할 수 있는 경우를 생각할 필요가 없기 때문이다.

퀸이 공격이 가능한 경우의 수 이후의 경우의 수는 가지치기를 하면 되는데

간단하게 말해서 그러한 경우의 수는 더이상 진행하지 않고 다음 경우의 수로 넘어가면 된다.

퀸이 공격 가능한 경우의 수

1. 같은 행에 있는 경우
2. 같은 열에 있는 경우
3. 같은 대각선에 있는 경우
4. 같은 역대각선에 있는 경우

위와 같은 4가지 경우의 수를 생각해보면 된다.

먼저 코드를 살펴보자.

static boolean isPossible(int[][] arr, int x, int y){
        // 세로 체크
        for (int i = 0; i < x; i++){
            if(arr[i][y] == 1){
                return false;
            }
        }
        // 대각선 체크
        for (int i = 1; i <= x; i++){
            if(y - i >= 0 && arr[x - i][y - i] == 1){
                return false;
            }
            if(y + i < arr.length && arr[x - i][y + i] == 1){
                return false;
            }
        }
        return true;
    }

위 코드의 경우는 같은 행의 경우를 체크하지 않는데 이는 행 마다 하나의 퀸만 놓일 수 있기 때문에
위 함수를 실행 하기전 행 마다 하나의 퀸만 놓일 수 있도록 하였다.

static int nQueen(int[][] arr, int depth){
        if(depth == arr.length){
            return 1;
        }
        int count = 0;
        for (int i = 0; i < arr.length; i++){
            if(isPossible(arr, depth, i)){
                arr[depth][i] = 1;
                count += nQueen(arr, depth + 1);
                arr[depth][i] = 0;
            }
        }
        return count;
    }

위 코드는 DFS를 사용하여 퀸을 놓는 경우의 수를 구하는 코드이다.

위 코드에서 isPossible 함수를 사용하여 가지치기를 해주고 있다.

depth 는 행을 의미하고 i는 열을 의미한다.

행의 끝까지 함수가 실행 될 경우 옳은 경우의 수이기 때문에 1을 반환하고

옳지 않은 경우 count 가 0이기 때문에 0을 반환한다.

또한 모든 경우의 수를 구해야 하기 때문에 arr[depth][i] = 1; 을 통해 퀸을 놓고

arr[depth][i] = 0; 을 통해 퀸을 빼주고 다음 경우의 수를 구해야 한다.

예시를 통해 코드를 이해해보자.

아래는 4 * 4 의 체스판이다.

1	0	0	0
0	0	1	0
0	0	0	1
0	1	0	0

• 첫 번째 depth가 0일 때 에서 0,0 을 선택하면 1,1 은 공격이 가능 하다 따라서 1,1 은 선택 할 수 없다. 따라서 가지 치기 된다.
• 0,0을 선택 할 경우 1,2 는 공격이 불가능 하다 따라서 선택이 가능하다.
• 0,0을 선택 할 경우 1,3 은 공격이 불가능 하다 따라서 선택이 가능하다.

이런 식으로 필요 없는 경우의 수는 가지치기를 해주고 옳은 경우의 수를 구해준다.

그리고 함수가 종료 조건 까지 실행 되고 나서 재귀함수의 이전 스택으로 돌아가게 되는데 여기서 arr[depth][i] = 0; 을 통해 퀸을 빼준다.

전체 코드

package org.example.boj;

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

public class Nqueen백트래킹9663 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        System.out.println(nQueen(arr, 0));
    }

    static int nQueen(int[][] arr, int depth){
        if(depth == arr.length){
            return 1;
        }
        int count = 0;
        for (int i = 0; i < arr.length; i++){
            if(isPossible(arr, depth, i)){
                arr[depth][i] = 1;
                count += nQueen(arr, depth + 1);
                arr[depth][i] = 0;
            }
        }
        return count;
    }

    static boolean isPossible(int[][] arr, int x, int y){
        // 세로 체크
        for (int i = 0; i < x; i++){
            if(arr[i][y] == 1){
                return false;
            }
        }
        // 대각선 체크
        for (int i = 1; i <= x; i++){
            if(y - i >= 0 && arr[x - i][y - i] == 1){
                return false;
            }
            if(y + i < arr.length && arr[x - i][y + i] == 1){
                return false;
            }
        }
        return true;
    }
}