[BOJ] 백준 2580번 - 스도쿠 풀이

| |
백준 온라인 저지 백준 2580번 - 스도쿠 C++ 풀이


문제

스도쿠는 18세기 스위스 수학자가 만든 ‘라틴 사각형’이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

1

나머지 빈 칸을 채우는 방식은 다음과 같다.

  1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
  2. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

2

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

3

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

4

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.


입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.


출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.


풀이

아주 흥미로운 문제였다. 해결 방법은 백트래킹으로, 빈 칸에 숫자를 닥치는대로 넣어보면서 빈 칸이 모두 채워질 때까지 이를 반복하는 것이다.

스도쿠 판의 (r,c) 좌표에 숫자 n 을 넣을 수 있는지에 대한 판단은 다음과 같은 과정으로 이루어진다.

  • r행에 이미 숫자 n 이 존재하는가?
  • c열에 이미 숫자 n 이 존재하는가?
  • 해당 좌표가 속한 3 × 3 구역에 이미 숫자 n 이 존재하는가?

위 3가지 중 하나라도 해당된다면 숫자 n 을 넣을 수 없으므로 n+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
#include <iostream>
using namespace std;

int board[9][9];

// (y,x) 좌표에 n 이 들어갈 수 있는 지 확인
bool check(int y, int x, int n){
  for(int i=0;i<9;i++){
    if(board[y][i]==n) return false;
    if(board[i][x]==n) return false;
  }

  for(int i=(y/3)*3; i<(y/3)*3+3; i++)
    for(int j=(x/3)*3; j<(x/3)*3+3; j++)
      if(board[i][j]==n) return false;

  return true;
}

void solve(int y, int x){
  // 좌표 조정
  if(x==9) {y++; x=0;}

  // 스도쿠 끝까지 도달 시
  if(y==9){
    for(int i=0;i<9;i++){
      for(int j=0;j<9;j++)
        cout<<board[i][j]<<" ";
      cout<<endl;
    }
    exit(0);
  }

  // 이미 채워져있으면 패스
  if(board[y][x]!=0){
    solve(y,x+1);
    return;
  }

  // 백트래킹
  for(int i=1;i<=9;i++){
    if(check(y,x,i)){
      board[y][x]=i;
      solve(y,x+1);
      board[y][x]=0;
    }
  }
}

int main(){
  for(int i=0;i<9;i++)
    for(int j=0;j<9;j++)
      cin>>board[i][j];

  solve(0,0);

  return 0;
}
0%