[백준] 9663번 - N-Queen [Java]

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

 

[백준] 9663번 - N-Queen [Java]

[백준] 9663번 - N-Queen [Java]

---

1.  아이디어

 

순열에 기반한 재귀 메서드와 방문 체크를 통해 해결할 수 있다.

순열의 depth를 열, 값을 행에 매핑해서 행과 열에 대한 중복을 미리 제거하고 대각선은 행과 열의 합과 차를 통해 방문 체크를 적용할 수 있다.

---

2. 문제풀이

 

0부터 N-1까지의 수 중에서 N개를 중복없이 뽑는 순열을 적용하면 바로 행과 열에 대한 중복 없는 퀸의 배치들을 얻을 수 있다. 이때 같은 대각선에 있는지 파악하는 방법은 우상좌하 대각선에서 같은 대각선에 있으면 행과 열의 합이 동일하고, 좌상우하 대각선에서 같은 대각선에 있으면 행과 열의 차가 동일하다는 점으로 백트래킹을 적용하는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;

public class Main {

    private static int N;
    private static boolean[] col;
    private static boolean[] d1;
    private static boolean[] d2;
    private static int cnt = 0;

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

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

        // 열에 대한 방문 체크 배열
        col = new boolean[N];

        // 우상좌하 대각선에 대한 방문 체크 배열
        d1 = new boolean[2 * N - 1];

        // 좌상우하 대각선에 대한 방문 체크 배열
        d2 = new boolean[2 * N - 1];

        solve(0);

        System.out.println(cnt);
    }

    // 순열 기반의 재귀 메서드로 selIdx 자체가 행에 대한 선택
    private static void solve(int selIdx) {
        if (selIdx == N) {
            cnt++;
            return;
        }

        for (int i = 0; i < N; i++) {
            if (col[i] || d1[i + selIdx] || d2[N - 1 + i - selIdx]) continue;

            col[i] = true;
            d1[i + selIdx] = true;
            d2[N - 1 + i - selIdx] = true;

            solve(selIdx + 1);

            col[i] = false;
            d1[i + selIdx] = false;
            d2[N - 1 + i - selIdx] = false;
        }
    }

}

---

4. 후기