9663번: N-Queen

문제

크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제입니다. 체스에서 퀸은 상하좌우, 그리고 대각선 8방향으로 거리 제한 없이 이동할 수 있습니다. 즉, 어떤 퀸을 놓았을 때 같은 행, 같은 열, 같은 대각선 상에는 다른 퀸을 놓을 수 없습니다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 N이 주어집니다. (1 ≤ N < 15)
• 출력: 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력합니다.

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

풀이: 1차원 배열을 활용한 상태 압축과 백트래킹

2차원 배열(N x N)을 사용하여 체스판을 모사하는 대신, 1차원 배열만으로 퀸의 위치를 기록하여 공간 복잡도와 탐색 시간을 극적으로 단축시킨 훌륭한 백트래킹 풀이입니다.

• 상태 압축 (1차원 배열 arr): 배열의 인덱스(i)를 '행(Row)'으로, 배열의 값(arr[i])을 '열(Column)'로 정의합니다. 예를 들어 arr[0] = 2는 0번째 행의 2번째 열에 퀸이 존재한다는 뜻입니다. 이 방식을 사용하면 '같은 행에 퀸을 두지 않는다'는 조건이 1차원 배열의 구조적 특성상 자연스럽게 만족됩니다.
• 백트래킹 (go 함수):
  • idx는 현재 퀸을 배치할 행을 의미합니다.
  • 0부터 N-1까지의 열(i)을 순회하며, 현재 행 idx의 i번째 열에 퀸을 임시로 배치해 봅니다. (arr[idx] = i)
  • 방금 놓은 퀸의 위치가 유효한지 check(idx) 메서드를 통해 검증합니다. 유효하다면(true), 다음 행(idx + 1)으로 넘어가 재귀 탐색을 이어갑니다.
  • idx == n에 도달하면 모든 행에 퀸을 무사히 배치한 것이므로 정답(ans)을 1 증가시키고 종료합니다.
• 유효성 검사 (check 함수): 방금 배치한 idx행의 퀸이 이전 행(0 ~ idx-1)들에 배치된 퀸들과 충돌하는지 검사합니다.
  1. 같은 열 검사: arr[i] == arr[idx] 이면 같은 열에 위치하므로 false를 반환합니다.
  2. 대각선 검사: 두 점의 '행의 차이'와 '열의 차이'가 같다면 대각선 상에 위치한다는 수학적 성질을 이용합니다. Math.abs(arr[i] - arr[idx]) == Math.abs(i - idx) 라면 false를 반환합니다.

코드

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

public class Main {
    static int ans, n;
    static int[] arr;

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

       n = Integer.parseInt(br.readLine());
       arr = new int[n];
       
       // 0번째 행부터 퀸 배치 시작
       go(0);

       bw.write(ans + "");

       bw.flush();
    }

    static void go(int idx) {
       // N개의 퀸을 모두 배치하는 데 성공한 경우 (Base Case)
       if (idx == n) {
          ans++;
          return;
       }

       // 현재 행(idx)의 0부터 N-1번째 열까지 퀸을 놓아봄
       for (int i = 0; i < n; i++) {
          arr[idx] = i;
          
          // 유망성 검사: 방금 놓은 퀸이 공격받지 않는다면 다음 행으로 진행
          if (check(idx)) {
             go(idx + 1);
          }
       }
    }

    // 현재 놓은 퀸(idx 행)이 위쪽 행들의 퀸과 충돌하는지 검사
    static boolean check(int idx) {
       for (int i = 0; i < idx; i++) {
          // 1. 같은 열에 퀸이 존재하는지 확인
          if (arr[i] == arr[idx])
             return false;
          // 2. 대각선 상에 퀸이 존재하는지 확인 (가로 길이와 세로 길이가 같은지)
          if (Math.abs(arr[i] - arr[idx]) == Math.abs(i - idx))
             return false;
       }

       return true;
    }
}

알고리즘 분류

브루트포스 알고리즘 (Brute Force), 백트래킹 (Backtracking)