Even Idiots Can Make Game

백준 9663 G4 N-Queen

Date/Lastmod
2025-06-04
Section
PS
Title
백준 9663 G4 N-Queen
Ps-Tags
backtrackingcsp
Solved
2025-03-162025-06-032025-06-04

#1 접근

쉽게 문제에 접근하기 위한 꽤 중요한 아이디어는 한 열에는 퀸이 딱 하나만 배치될 수 있다는 것이다.

한 열에 퀸을 배치하고, 다음 열에는 행이 겹치지 않게 퀸을 배치하고, 이런 식으로 반복하면 $N(N−1)(N−2)…1=N!$의 경우의 수가 있을 것이다. 이는 $O(N!)$의 무시무시한 복잡도이지만, 시간 제한이 10초이기 때문에 괜찮다.

때문에 이 문제는 완전 탐색으로 가능한 모든 해의 공간을 탐색하되, 유망하지 않은 분기를 판단하기 쉬우므로 백 트래킹을 적용하면 쉽게 풀 수 있다.

#1 알고리즘

위에서도 이야기했듯, 문제에 쉽게 접근하려면 한 열에는 퀸이 딱 하나만 배치될 수 있다는 아이디어가 꽤 중요하다.

이 말은, 전체 체스판의 상태를 1차원 배열 하나로 표현할 수 있다는 뜻이다. 예를 들어, 크기 N짜리 vector<int> queen 을 만들었다고 가정하자. 그러면 queen[i] == j 라면 i 행에서 퀸의 위치는 j 라는 뜻이다.

0번 열부터 시작하여 퀸을 배치해 본다. 퀸을 배치하면 체스판의 상태가 바뀌며, 결정 트리 내에서 가능성이 분기한다.

예를 들어, N = 5 인 경우, 0번 열 부터 시작하여, 현재 4번 열에 배치하려고 한다면, 위와 같은 분기가 일어날 것이다. 네번째 노드를 제외한 나머지 넷은 체스의 규칙상 배치를 할 수 없는 곳에 배치를 한 것이므로, 더 이상 진행할 수 없는 Dead-End 노드이다. 이러한 Dead-End 노드에서는 이전의 선택으로 복귀하기 위해 백 트래킹을 수행한다. 마지막 열인 4번 열까지 배치를 진행했고, 체스의 규칙을 위반하지 않았다면, 모든 배치에 성공한 것이므로, ‘퀸을 배치할 수 있는 경우의 수’를 하나 증가시킨다.

깊이 우선 탐색을 통해 결정 트리를 순회하며 백 트래킹 하는 함수 bt(v) 는 다음처럼 작동한다.

이를 코드로 표현한다면 아래와 같다.

void bt(int v) {
  // 마지막 열인가?
  if (v == N) {
    ++cnt;
    return;
  }

  for (int h = 0; h < N; ++h) {
    if (!is_safe(v, h)) {
      continue;
    }
    queen[v] = h;
    bt(v + 1);
  }
}

queen[v] = -1 은 사실 없어도 상관 없지만, (덮어 쓰기 때문) 백 트래킹이 일어났다는 것을 보여주기 위해 추가하였다.

#2 is_safe 함수의 설계

퀸을 배치해도 문제가 없는지 판단하는 함수 is_safe 는 다음처럼 설계한다.

bool is_safe(int v, int h) {
  for (int pv = 0; pv < v; ++pv) {
    int ph = queen[pv];

    // 이전 열에 배치된 퀸퀸 중 하나의 위치가 pv열 ph행이다.
    // 현재 v열 h행에 새 퀸을 배치할 수 있는지 확인한다.

    // 같은 행에 놨는지 검사
    if (ph == h) {
      return false;
    }    

    // 대각선이 겹치는지?
    if (abs(pv - v) == abs(ph - h)) {
      return false;
    }

  }
  return true;
}

여기서 두 퀸이 대각 방향으로 서로 공격할 수 있는지 판단하기 위한 로직이 눈여겨 볼 만 하다.

좌 상단, 좌 하단, 우 상단, 우 하단 대각선에 존재하는지 확인하려면, 두 퀸의 행 번호 차이의 절대값과, 열 번호 차이의 절대값이 같은지 확인하면 된다.

#1 코드

전체 코드는 아래와 같다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N;

// queen[i] = j 면,  i열 j행에 배치되어 있다는 뜻
vector<int> queen; 

int cnt = 0;

bool is_safe(int v, int h) {
  for (int pv = 0; pv < v; ++pv) {
    int ph = queen[pv];

    // 이전 열에 배치된 퀸퀸 중 하나의 위치가 pv열 ph행이다.
    // 현재 v열 h행에 새 퀸을 배치할 수 있는지 확인한다.

    // 같은 행에 놨는지 검사
    if (ph == h) {
      return false;
    }    

    // 대각선이 겹치는지?
    if (abs(pv - v) == abs(ph - h)) {
      return false;
    }

  }
  return true;
}

void bt(int v) {
  // 마지막 열인가?
  if (v == N) {
    ++cnt;
    return;
  }

  for (int h = 0; h < N; ++h) {
    if (!is_safe(v, h)) {
      continue;
    }
    queen[v] = h;
    bt(v + 1);
  }
}

int main() {
  cin >> N;
  queen.resize(N);
  fill(queen.begin(), queen.end(), -1);

  bt(0);

  cout << cnt;
}

#1 제약 만족 문제(CSP, Constraint Satisfaction Problem)

N-Queen은 사실 제약 만족 문제(CSP, Constraint Satisfaction Problem)이다. CSP는 여러 변수에 값을 할당하되, 제약 조건을 모두 만족시키는 해를 찾는 문제이다. 핵심은 모든 변수에 충돌 없이 값을 배정하는 것이다.

N-Queen 문제를 CSP로 해석하면 다음과 같다.

CSP 해 공간이 매우 크다는 특징이 있고, 대체로 백 트래킹을 이용해 제약 조건을 만족하지 않으면 이전 분기로 되돌아가는 풀이를 사용한다.

대표적인 CSP 문제로 N-Queen, 스도쿠, 그래프 색칠, 시간표 작성 문제가 있다.

comments powered by Disqus