[BOJ] 9663번 : N-Queen (JAVA/자바)

문제

---

알고리즘 고민

퀸은 가로, 세로, 4방향의 대각선으로 공격이 가능하다.

출처 : https://opentutorials.org/module/3806/22853

따라서 퀸을 놓을 수 있는지 확인하려면 놓는 위치에서 위에 해당하는 범위에 다른 퀸이 있는지 확인을 해야한다. 없다면, 놓는 퀸이 다른 퀸을 공격할수도, 다른 퀸이 놓는 퀸을 공격할수도 없을것이다.

 

처음에는 dfs 통해 N x N 배열을 돌면서 퀸을 한쪽에 놓고 그 위치에서부터 배치가 가능한지 위의 공격범위로 총 8방향을 검사하면서 진행했다. 하지만, N이 8만 되도 시간이 엄청나게 드는것을 확인할 수 있었다. 이후 다른 방법에 대해 생각을 했다.

 

퀸을 배치할때, 가로나 세로 부분에 한부분은 무조건 차지하기 때문에 사실 배열이 2차원이 아닌 1차원 배열로도 표현을 압축해서 하는 것이 가능하다는 것을 확인했다. 

세로	1	2	3	4	5	6	7	8
가로	8	4	1	3	6	2	7	5

위의 표처럼 1차원 배열의 인덱스를 세로위치 혹은 가로위치로 생각을 하고 그 안에 값으로는 다른 값을 넣어주면 퀸의 위치가 표현 가능했다. 표현을 압축해서 했다면 압축된 표현 내에서 퀸을 놓을때 놓을수 있을지 없을지에 대한 검사를 어떻게 할 것인지에 대한 고민이 필요했다.

 

우선 위의 표처럼 세로를 배열의 인덱스로 놨다면 세로는 겹칠일이 없기 때문에 고려할 필요가 없었다. 그 다음으로는 가로를 검사해야 하는데 이 경우에도 간단했다. dfs 하는 과정에서 앞쪽의 1 위치부터 순차적으로 놓는 방법을 택했기 때문에 놓으려는 n 위치의 퀸은 n-1 까지 숫자가 겹치는 것이 있는지 단순하게 검사하면 됬다. 

 

다음으로는 조금 어려웠던 대각선 검사방법인데, 대각선은 기울기가 같은 위치에 존재하는 말이 있는지 검사를 진행해야했다. 기울기는 세로/가로 인데 단순히 세로/가로 를 해서 검사하면 5/4 처럼 나머지가 있는 값들이 사라지기 때문에 

(N위치의 가로 - i번째 검사할 말의 가로) 와 (N위치의 세로 - i번째 검사할 말의 세로) 를 비교하는 방법을 채택했다. 이때 값들에 절대값을 씌워주어야 하는데 대각선이 우하향하거나 좌상향하는 경우에는 둘의 값이 똑같기 때문에 상관 없지만 우상향하거나 좌하향하면 서로 부호가 다르기 때문이다.

 

이런 방법을 이용해서 알고리즘을 구성하였다.

---

JAVA Code

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

public class Main {
    static int[] queenHeightIdx;
    static int N, cnt;

    public static void dfsBatch(int idx) {
        if (idx == N+1) {
            cnt++;
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (canBatch(idx, i)) {
                queenHeightIdx[idx] = i;
                dfsBatch(idx + 1);
            }
        }
    }

    public static boolean canBatch(int w, int h) {
        for (int i = 1; i < w; i++) {
            if (queenHeightIdx[i] == h) {
                return false;
            }

            int row = i - w;
            int col = queenHeightIdx[i] - h;
            if (Math.abs(row) == Math.abs(col)) {
                return false;
            }
        }

        return true;
    }

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

        N = Integer.parseInt(br.readLine());
        queenHeightIdx = new int[N + 1];
        cnt = 0;

        dfsBatch(1);

        System.out.println(cnt);
    }
}