[ 백준 ] 9663 N-Queen (Java 자바)

🔗 문제 링크: 백준9663번 N-Queen

문제 설명

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

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

입력 조건

• 입력:
  • 체스판의 크기 N (즉, 배치할 퀸의 개수와 동일한 N×N 체스판)

---

풀이 과정

📌 문제 요약

• 체스판의 각 행마다 하나의 퀸을 배치하는 경우의 수를 DFS(백트래킹)를 통해 탐색한다.
• 퀸이 서로 공격하지 않도록 하기 위해, 같은 열 및 두 대각선(우하단, 좌하단)에 퀸이 있는지 여부를 체크한다.

📌 해결 전략

1. 열 및 대각선 체크 배열 사용:
   • 열(col): 이미 특정 열에 퀸이 배치되었는지 여부를 기록한다.
   • 우하단 대각선(slash): (row + col)이 동일하면 같은 우하단 대각선에 속하므로, 해당 값 인덱스로 체크한다.
   • 좌하단 대각선(bSlash): (row - col + N)을 인덱스로 사용하여, 같은 좌하단 대각선에 퀸이 있는지 체크한다.
     이처럼 세 가지 배열을 사용하면, 현재 (row, col)에 퀸을 배치해도 안전한지 O(1) 시간에 판단할 수 있다.
2. DFS를 이용한 행별 탐색:
   • 1행부터 N행까지 순차적으로 진행하며, 각 행에서 가능한 열을 시도한다.
   • 만약 해당 위치가 안전하면(열, 대각선 조건을 모두 만족하면) 해당 위치에 퀸을 배치하고 다음 행으로 진행한다.
   • 모든 행에 퀸을 배치한 경우 해를 하나 찾은 것으로 처리한다.
3. 백트래킹:
   • DFS 재귀 호출 후에는 선택했던 상태(열, 대각선에 배치 표시)를 복구하여 다른 경우의 수를 탐색한다.
   • 한 경로에서 선택한 결과가 이후 경로에 영향을 주지 않도록 한다.

📌 풀이 과정 (백트래킹)

• 재귀 함수 setQueens(rowNo):
  • 기저조건 : rowNo > N이면 모든 행에 퀸을 배치한 것이므로 해의 개수를 1 증가시킨다.
  • 각 행의 모든 열을 순회하며, 현재 위치 (rowNo, c)가 안전한지 isAvailable(rowNo, c)로 확인한다.
  • 안전하다면 해당 열과 두 대각선에 퀸 배치를 표시한 후, 다음 행에 대해 재귀 호출하고, 재귀 호출이 끝나면 상태를 복구한다.
• 안전성 판단 함수 isAvailable(rowNo, c):
  • 열, 우하단 대각선, 좌하단 대각선 배열을 이용해 현재 위치에 이미 다른 퀸이 배치되어 있는지를 O(1) 시간에 판단한다.
  • 이 방법은 DFS의 각 분기마다 중복되는 검사를 줄여 전체 탐색 효율을 높인다.

📌 시간 복잡도 분석

• DFS는 각 행마다 최대 N개의 선택지를 가지며, 전체 경우의 수는 최악의 경우 O(N!)이다.
• 하지만, 열과 대각선 체크를 통해 불가능한 경우를 빠르게 가지치기하므로 실제 탐색하는 경우의 수는 훨씬 줄어든다.
• N의 최대값이 작기 때문에(일반적으로 10~15 사이) 이 방법은 충분히 시간 내에 동작한다.

---

🔥 최종 정리 및 코드

• 열 및 대각선 체크 배열:
  • 빠른(상수 시간) 안전성 검사를 위해 열과 두 대각선의 상태를 별도의 불린 배열에 저장하였다.
  • 이는 DFS 재귀 호출 시 현재 위치가 공격받는지 즉시 판단할 수 있어, 불필요한 탐색을 줄이는 중요한 최적화 포인트이다.
• DFS와 백트래킹:
  • 각 행마다 가능한 열을 순회하며 퀸을 배치하고, 재귀적으로 다음 행을 탐색한다.
  • 선택 후 반드시 상태를 복구하는 백트래킹을 통해 다른 경우의 수를 올바르게 탐색할 수 있다.

package Graph;

import java.util.Scanner;

/*
 * N x N 체스판에 N개의 퀸을 서로 공격하지 않도록 배치하는 문제 (N-Queen 문제)
 */

public class BOJ_G4_9663 {
    static int N;         // 체스판의 크기 (행과 열의 수), 동시에 배치할 퀸의 개수
    static int ans;       // 가능한 퀸 배치 방법의 총 개수를 저장하는 변수
    // 각 배열은 해당 열 또는 대각선에 퀸이 배치되어 있는지 여부를 저장 (true: 배치됨)
    static boolean[] col;     // 열 검사: 인덱스 1 ~ N 사용 (0번 인덱스는 사용하지 않음)
    static boolean[] slash;   // 우하단 대각선 검사: (row + col)의 값이 동일하면 같은 대각선, 범위: 2 ~ 2*N, 크기는 2*N+1
    static boolean[] bSlash;  // 좌하단 대각선 검사: (row - col + N)를 인덱스로 사용, 범위: 1 ~ 2*N-1, 크기는 2*N

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 사용자로부터 체스판 크기 N 입력받기
        N = sc.nextInt();
        
        // 열 상태 배열 초기화: 1부터 N까지 사용 (0번 인덱스는 사용하지 않음)
        col = new boolean[N + 1];
        // 우하단 대각선 배열 초기화: 인덱스 0부터 2*N까지 사용 (합이 2부터 2*N까지 가능)
        slash = new boolean[2 * N + 1];
        // 좌하단 대각선 배열 초기화: 인덱스 0부터 2*N-1까지 사용
        bSlash = new boolean[2 * N];

        // 1행부터 시작하여 재귀적으로 퀸을 배치
        setQueens(1);
        // 가능한 모든 배치 방법의 개수를 출력
        System.out.println(ans);
    }
    
    /**
     * rowNo 행에 퀸을 배치하는 재귀 함수 (백트래킹)
     * @param rowNo 현재 배치할 행 번호 (1부터 시작)
     */
    private static void setQueens(int rowNo) {
        // 기저 조건: 모든 행에 퀸을 배치했다면 한 가지 해를 찾은 것
        if (rowNo > N) {
            ans++;
            return;
        }
        
        // 현재 행의 각 열에 대해 퀸 배치 시도
        for (int c = 1; c <= N; c++) {
            // (rowNo, c) 위치가 안전한지 검사
            if (!isAvailable(rowNo, c))
                continue;
            
            // 현재 위치에 퀸 배치 후 해당 열과 대각선에 표시
            col[c] = true;
            slash[rowNo + c] = true;
            bSlash[rowNo - c + N] = true;
            
            // 다음 행으로 진행
            setQueens(rowNo + 1);
            
            // 백트래킹: 현재 배치 상태를 복구하여 다른 경우의 수 탐색
            col[c] = false;
            slash[rowNo + c] = false;
            bSlash[rowNo - c + N] = false;
        }
    }
    
    /**
     * (rowNo, c) 위치에 퀸을 배치할 수 있는지 확인하는 함수.
     * 이미 같은 열 또는 대각선에 퀸이 배치되어 있다면 false를 반환.
     *
     * @param rowNo 현재 행 번호
     * @param c 현재 열 번호
     * @return 해당 위치가 안전하면 true, 아니면 false
     */
    private static boolean isAvailable(int rowNo, int c) {
        // 조건:
        // 1. 해당 열(col[c])에 퀸이 배치되어 있지 않아야 함.
        // 2. 우하단 대각선(slash[rowNo+c])에 퀸이 배치되어 있지 않아야 함.
        // 3. 좌하단 대각선(bSlash[rowNo-c+N])에 퀸이 배치되어 있지 않아야 함.
        return !col[c] && !slash[rowNo + c] && !bSlash[rowNo - c + N];
    }
}