[백준] 9663 : N-Queen (JAVA)

난이도

🥇 4

 

링크

https://www.acmicpc.net/problem/9663

9663번: N-Queen

---

문제

---

풀이과정

해당 문제는 백트래킹을 사용하는 문제이다.

 

백트래킹이란 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다. 

즉, 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 모든 경우의 수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가기 때문에 모든 노드를 확인하는 것이 아니라는 점이 브루트포스 알고리즘과의 차이점이다.

 

위의 특징을 가지고 문제를 풀어보자면

우선 체스판에서 '퀸이 서로 공격할 수 없도록 배치하는 경우의 수'를 구하는 문제였기에

퀸이 이동할 수 있는 위치를 먼저 확인해보면 된다.

 

퀸은 상하좌우 및 대각선으로 거리 제한 없이 한 방향으로 이동이 가능하다는 특징이 있다.

그렇다면 이러한 특징을 그림으로 살펴보면 다음과 같다.

 

위의 이동가능한 동선과 겹치지 않는 곳에 다른 퀸을 배치하는 것이 중점이다.

 

 

그렇다면 4x4 체스판에서 퀸이 어떻게 놓일 수 있는지 확인해보자.

1) 우선 0번째 행, 0번째 열에 퀸이 있다고 가정한다.

해당 위치에 퀸이 놓여져 있을 때 X 표시가 된 곳에는 또 다른 퀸이 놓일 수 없다. 즉 남은 공간에 넣어야 된다.

 

2) 다음 열에서 2번째 행에 퀸을 놓았다고 가정한다.

 두 번째 행이 이동가능한 경로를 모두 X 표시하면 최종적으로 남는 공간은 하나가 남는다.

 

3) 결국 4x4 체스판에서 경우의 수 중 하나는 다음과 같은 결과가 나온다.

 

위의 과정처럼 각 행 별로 놓을 수 있는 위치에 있을 때 재귀호출을 해주고, 모두 배치되었을 때 count를 해주면서 경우의 수를 찾아내는 것이다.

---

 

처음에 체스판을 2차원 배열로 만들어야 된다고 생각했는데 1차원 배열로 만들어도 됐었다!

배열의 크기가 행의 크기가 되고 각 인덱스에 있는 값은 열을 의미하는 것이다.

 

그 이유는 퀸이 갈 수 있는 위치가 상하좌우 및 대각선이기 때문에 각 행에 퀸이 1개만 들어갈 수 있기 때문이다.

 

 

만약 chess 배열에 [0 3 1 2] 이라는 값이 들어가 있다고 가정하면 

0번째 행 ➡️ 0번째 열 / 1번째 행 ➡️ 3번째 열 / 2번째 행 ➡️ 1번째 열 / 3번째 행 ➡️ 2번째 열

위와 같이 체스판이 구성되어 있는 것이다.

 

이후 아래의 코드처럼 depth(행)를 하나씩 늘려가며 possibility 함수를 실행시킨다. 

possibility 함수는 해당 위치에 퀸을 위치해도 되는지 확인하는 역할이다.

해당 함수에서 true가 반환되면, 위치가 적합하기 때문에 다음 행으로 이동하기 위해 depth + 1 해준다.

for (int i = 0; i < N; i++) {
    chess[depth] = i;
    if (possibility(depth)) {
        nQueen(depth + 1);
    }
}

 

possibility 함수에서 고려해줘야 하는 것은 같은 열과 대각선에 퀸이 있는지 없는지 판별해주면 된다.

if문은 같은 열에 일치하는게 있는지 판별하는 역할이고

else if 문은  대각선에 일치하는게 있는지 판별하는 역할이다.

for (int i = 0; i < col; i++) {
    if (chess[col] == chess[i]) {
        return false;
    }
    else if (Math.abs(col - i) == Math.abs(chess[col] - chess[i])) {
        return false;
    }
}

 

[0 3 1 2] 에서 2번째 행과 3번째 행을 비교하였을 때

Math.abs(3 - 2) == Math.abs(chess[3] - chess[2]) ➡️ 1 == 1 ➡️ false

이기 때문에 대각선에 일치하는게 있다는 의미로 해당 부분에 퀸을 배치할 수 없는 것이다!

 

이후 depth(행)이 N과 같아지면 N개의 퀸이 다 배치되었다는 것이기 때문에 함수를 종료하며

최종적인 결과값인 '퀸이 서로 공격할 수 없도록 배치하는 경우의 수'를 출력하면 되는 것이다.

---

전체 코드

import java.io.*;
import java.util.*;

public class Main {

    private static int[] chess;

    private static int N;
    private static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        chess = new int[N];

        nQueen(0);

        System.out.println(count);
    }

    private static void nQueen(int depth) {
        if (depth == N) {
            count++;
            return;
        }

        for (int i = 0; i < N; i++) {
            chess[depth] = i;
            if (possibility(depth)) {
                nQueen(depth + 1);
            }
        }
    }

    private static boolean possibility(int col) {
        for (int i = 0; i < col; i++) {
            if (chess[col] == chess[i]) {
                return false;
            }
            else if (Math.abs(col - i) == Math.abs(chess[col] - chess[i])) {
                return false;
            }
        }

        return true;
    }
}

 

결과