[9663] N-Queen

🔗 문제 링크

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

🔍 문제 설명

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

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

⚠️ 제한사항

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

🗝 풀이 (언어 : Java)

상당히 어려웠던 문제다. BackTracking 문제인데, DFS로 전체 경우를 찾지만 모든 케이스를 찾으면 너무 시간이 많이 소요되므로, 중간에 정답 가능성이 없는 케이스는 재귀 호출을 하지 않도록 하는 것이다. 풀이를 공부하고 다시 작성해 보았다. 한 줄의 행에 한개씩만 퀸을 놓을 수 있는 것을 이용해서, 행 위치를 기준으로 반복한다. 해당 row라는 행에 i라는 열위치에 퀸을 놓고, 전의 row들에 놓았던 퀸들의 위치를 가져와서 현재 위치 & 전의 위치 1개씩 서로 공격가능한 위치에 있는지 체크한다. 한개라도 존재하면 해당 row와 i에 퀸을 놓는 케이스는 정답이 될 수가 없으므로 다음 행에 퀸을 놓는 재귀 호출을 중단한다. 두 좌표가 서로 공격 가능한지는 열은 반복문으로 한줄에 하나씩만 놓으므로 겹칠 수가 없고, 행이 같은지 비교, 대각선은 행과 열의 좌표 차이 또는 합이 같다면 두가지의 대각선 방향중 공격 가능한 위치에 존재한다는 것을 알아야 한다.

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

class Main {
    private static int answer = 0;
    // 두 좌표의 놓인 퀸이 서로 공격할 수 있는 위치에 있으면 true
    private boolean invalid(int r1, int c1, int r2, int c2) {
        // 열이 같으면 탈락
        if (c1 == c2) return true;
        // 우상향, 좌상향 대각선 방향에 있으면 탈락
        if (r1 - c1 == r2 - c2) return true;
        if (r1 + c1 == r2 + c2) return true;
        return false;
    }

    private void nQueen(int n, int row, int[] col) {
        // 모든 row(0 ~ n-1)에 퀸을 놓는 것을 성공하면 카운트
        if (row == n)
            answer++;
        // row(0 ~ n-1)에 퀸을 놓기
        else {
            // i는 해당 row에서 선택한 col 인덱스
            for (int i = 0; i < n; i++) {
                boolean flag = true;
                // j는 i전에 놓았던 퀸의 row, col을 구하기 위함
                for (int j = 0; j < row; j++) {
                    // 전에 놓았던 퀸들과 현재 후보위치 퀸이 공격 불가능한 위치인지 확인
                    if (invalid(row, i, j, col[j])) {
                        flag = false;
                        break;
                    }
                }
                // 해당 row의 퀸과 전의 퀸들이 유효한 위치라면 다음 row로
                if (flag) {
                    col[row] = i;
                    nQueen(n, row + 1, col);
                    col[row] = 0;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main main = new Main();
        int n = Integer.parseInt(br.readLine());
        br.close();
        // 첫번째 줄(0) 부터 시작, col[row]은 해당 행에서 어디 열에 퀸을 놓았는지 표시
        main.nQueen(n, 0, new int[n]);
        System.out.print(answer);
    }
}