Even Idiots Can Make Game

백준 2239 G4 스도쿠

Date/Lastmod
Section
PS
Tags
backtrackingcsp
Title
백준 2239 G4 스도쿠
Ps-Tags
backtrackingcsp
Solved
06-02/25

#1 풀이

평소 스도쿠를 재미있게 하는 편이고 할 때마다 “스도쿠를 자동으로 풀어내는 알고리즘"에 대해 생각해보곤 했는데, 이렇게 문제로 만나버렸다.

무식하게 푼다고 가정하고, 모든 칸이 빈 칸이라고 생각해보자. 왼쪽 위위부터 차례대로 채워나간다고 할 때, 각 칸에 숫자를 채울 때는 다음 세 가지 제약 조건을 반드시 만족해야 한다.

숫자는 1부터 9까지 가능한 수 중에서, 위 제약 조건을 모두 만족하는 가장 작은 숫자를 채운다. (사전순으로 가장 앞선 숫자)

#1 탐욕적 접근으로는 항상 해에 도달하지 못한다

이건 매번의 판단에서 가장 적합한(3가지 제약을 만족하고, 사전순으로 가장 앞선) 숫자를 기입한다는 점에서 탐욕적 접근이다. 하지만 매 순간 탐욕적으로 숫자를 택하면, 스도쿠의 보드를 완성할 수 있을까?

#2 탐욕적 알고리즘이 성공하기 위한 조건

탐욕적 알고리즘이 성공하려면 다음 두 가지 조건이 있어야 한다.

  • 탐욕 선택 속성(Greedy Choice Property)
    • 문제를 풀 때 각 단계에서 최선이라고 생각되는 선택을 하는 것이, 전체 문제의 최적해로 이어진다는 보장이 있어야 한다. (전략적 확신)
  • 최적 부분 구조(Optimal Substructure)
    • 문제의 전체 최적해가, 그 하위 부분 문제들의 최적해로 구성된다. (구조적 속성)

예를 들어, 10, 50, 100, 500원짜리 동전이 무한히 있고, 거스름돈 760원을 최소 개수로 만들고 싶다. 탐욕적으로는 큰 동전부터 가능한 만큼 쓰면 해결할 수 있다. 이 예제에서 탐욕 선택 속성은 큰 동전을 먼저 쓰는게 항상 유리하다는 것이다. 그리고, 최적 부분 구조는 760원 문제를 500원을 쓰고, 나머지 260원을 푸는 하위 문제로 나눌 수 있다는 것이다.

하지만 반례로 1원, 3원, 4원으로 동전을 최소 갯수만 사용하여 6원을 만든다고 하자. 탐욕적으로 역시 큰 동전부터 가능한 만큼 쓰고 싶지 않은가? 4원을 1개, 1원을 2개 써서 3개가 최적해인 것 같지만, 사실 3원을 2개 쓰면 3개보다 적게 사용하여 6원을 만들 수 있다. 즉, 탐욕이 실패하였고, 실패 원인은 탐욕 선택 속성이 만족되지 않기 때문이다.

#2 스도쿠가 탐욕 알고리즘으로 풀 수 없음을 나타내는 반례

그러면 스도쿠는 탐욕 선택 속성이 있을까 없을까?

어떤 문제가 탐욕 선택 속성이 없는 것을 증명하기 위해서는 반례를 딱 하나만 찾아내면 된다. 그러니까, 지금 최선의 숫자라고 생각하여 선택했던 것이, 전체 스도쿠를 완성시키지 못하는 결과를 낳는 경우를 찾으면 된다.

다음과 같은 반례가 있다.

B1 3  4  5  6  7  8  B2 9
A  B  C  D  E  F  G  2  F
...

B1부터 칸을 채워나갈 것이고, B1에는 1 혹은 2가 들어올 수 있다. B1에 1을 넣어버리면, 나중에 탐색되는 B2의 운명은 2로 고정되어 버린다. 하지만, B2는 애초에 2가 들어갈 수 없는 자리이다. 하지만 우리는 이 사실을 B2에 가서야 알아차리게 된다.

#1 백 트래킹의 필요성

매 순간 탐욕적 선택으로는 해를 만들 수 없는 종단점(Dead-end)에 도달할 수도 있다는 것을 보았다.

때문에 위 반례에서 B2에서 *“아, 더이상 스도쿠를 채워나갈 수가 없구나”*라고 깨달았다면 이전 상태로 복기해야 하기 때문에 백 트래킹을 해야한다.

사실 스도쿠가 욕심쟁이 알고리즘으로 풀 수 없음을 생각해내는 것이 어렵지, 백 트래킹을 해야한다는 사실만 알았으면 풀이 자체는 쉬운 편이다.

위처럼, 아직 스도쿠를 다 완성하지도 않았는데 넣을 숫자가 없다면 지금 어딘가에서 잘못된 분기를 타고 들어온 이유로 전체 해를 완성할 수 없다는 의미이다.

그러므로, 백 트래킹을 하여 다시 탐색해야 한다.

#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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#include <iostream>
#include <array>
#include <string>

using namespace std;

const int BLANK{0};
array<array<int, 9>, 9> board;

/// @brief board[i][j]에 c가 들어갈 수 있는지 확인
bool check(int i, int j, int c) {
  for (int v{0}; v < 9; ++v) {
    if (c == board[v][j]) {
      return false;
    }
  }

  for (int h{0}; h < 9; ++h) {
    if (c == board[i][h]) {
      return false;
    }
  }

  int vp{(i / 3) * 3}, hp{(j / 3) * 3};

  for (int v{vp}; v < vp + 3; ++v) {
    for (int h{hp}; h < hp + 3; ++h) {
      if (c == board[v][h]) {
        return false;
      }
    }
  }

  return true;
}

bool DFS() {
  for (int i{0}; i < 9; ++i) {
    for (int j{0}; j < 9; ++j) {
      if (board[i][j] == BLANK) {

        for (int c{1}; c <= 9; ++c) {
          if (check(i, j, c)) {
            // 한 번 넣어본다
            board[i][j] = c;

            // 넣어본 상태로 탐사
            if (DFS()) { 
              // 여기에 도달하는 시점은 전체 문제를 해결하는 시점이다.
              return true; 
            }

            // 백 트래킹
            board[i][j] = BLANK;
          }
        } 

        // 이 칸에 어떤 수도 넣을 수 없었다면 여기에 도달하게 된다.
        return false; 
      }
    }
  }
  return true; 
}


int main() {
  // 입력
  for (int i{0}; i < 9; ++i) {
    string line; cin >> line;

    for (int j{0}; j < 9; ++j) {
      board[i][j] = line[j] - '0';
    }
  }

  // 풀이
  DFS();

  // 출력
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      cout << board[i][j];
    }
    cout << '\n';
  }
}
comments powered by Disqus