[BOJ-2580][C++] 스도쿠

문제

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

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

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

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

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

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

 

입력

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

 

출력

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

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

 

제한

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
  • C++14: 80ms
  • Java: 292ms
  • PyPy3: 1172ms

 

예제 입력 1

0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

 

예제 출력 1

1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

 

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 초등부 5번
Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 중등부 3번

 

알고리즘 분류

• 백트래킹

 

문제 출처

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

---

 

문제 해결 방법

• 백트래킹 알고리즘을 이용하여 문제를 해결하였다.

 

 입력 받은 인자를 이용하여 행 번호(row)와 열 번호(col) 구하기

• 입력 받은 수에서 행 번호는 cnt / 9 와 같이, 열 번호는 cnt % 9와 같이 계산하여 구할 수 있다.

int row = cnt / 9;    // 행 구하기
int col = cnt % 9;    // 열 구하기

• 스도쿠는 9 × 9 크기 2차원 배열로 이루어져 있으므로, 81(= 9 × 9)개의 인자들이 행 번호와 열 번호로 분리되어 배열에 입력될 것이다.

 

문제를 해결하기 위한 3가지 조건

• 스도쿠를 풀려면, 판(board)에 있는 모든 숫자들이 다음의 3가지 조건을 만족시켜야 한다.

① 각각의 가로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
② 각각의 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
③ 굵은 선으로 구분되어 있는 3×3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

• 빈 자리에 숫자를 넣으면서, 3가지 조건을 모두 만족할 경우 그 다음으로 진행하는 과정을 반복하도록 하여 문제를 해결하였다.

 

조건 ①, ② 해결하기

• 조건 ①과 조건 ②를 해결하기 위해 다음과 같이 코드를 작성하였다.
  • for 문을 돌리면서 같은 숫자가 있을 경우 false를 반환하도록 한다.

// (1) 행/열 체크
for (int i = 0; i < MAX_SIZE; i++) {
    if (board[row][i] == num) {    // 행 체크 : 같은 행에 동일한 숫자가 있을 경우
        return false;
    }
    if (board[i][col] == num) {    // 열 체크 : 같은 열에 동일한 숫자가 있을 경우
        return false;
    }
}

 

조건 ③ 해결하기

• 조건 ③을 해결하기 위해 다음과 같이 코드를 작성하였다.

// (2) 3x3 박스 체크
int startRow = (row / 3) * 3;
int endRow = (row / 3) * 3 + 3;
int startCol = (col / 3) * 3;
int endCol = (col / 3) * 3 + 3;

for (int i = startRow; i < endRow; i++) {
    for (int j = startCol; j < endCol; j++) {
        if (board[i][j] == num) {
            return false;
        }
    }
}

• 비어 있는 공간에 숫자를 하나씩 채워나가면서 이 3가지 조건을 모두 만족시키는지 확인한다.
  • 가지치기(Prunning)를 진행하면서 유망한(Promising) 해를 찾아나간다.

 

종료 조건

• 백트래킹을 진행하면서 함수의 인자(cnt)가 81(= 9 × 9)이 될 경우 프로그램을 종료시킨다.
• 이 때 주의할 점은, 프로그램을 반드시 exit(0); 으로 종료시켜야 한다는 것이다.
  • 그렇지 않을 경우, 모든 수를 0으로 넣을 경우 여러 가지 스도쿠 풀이가 반복적으로 출력된다.
  • 그래서 오직 1개의 풀이만 출력시킨 후 프로그램을 종료시키도록 하기 위해 exit(0); 문으로 프로그램을 종료시키도록 한다. 

if (cnt == 81) {
    Print();
    exit(0);    // 반드시 exit(0)으로 처리하여 강제 종료! (return으로 처리할 경우, 통과 불가)
}

 

반례 테스트 케이스

테스트 케이스 #1

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

 

출력 결과 #1

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2

 

테스트 케이스 #2

0 2 0 9 0 5 0 0 0
5 9 0 0 3 0 2 0 0
7 0 0 6 0 2 0 0 5
0 0 9 3 5 0 4 6 0
0 5 4 0 0 0 7 8 0
0 8 3 0 2 7 5 0 0
8 0 0 2 0 9 0 0 4
0 0 5 0 4 0 0 2 6
0 0 0 5 0 3 0 7 0

 

출력 결과 #2

3 2 1 9 7 5 6 4 8
5 9 6 8 3 4 2 1 7
7 4 8 6 1 2 9 3 5
1 7 9 3 5 8 4 6 2
2 5 4 1 9 6 7 8 3
6 8 3 4 2 7 5 9 1
8 1 7 2 6 9 3 5 4
9 3 5 7 4 1 8 2 6
4 6 2 5 8 3 1 7 9

 

코드

#include <iostream>
using namespace std;

#define MAX_SIZE 9

int board[MAX_SIZE][MAX_SIZE];

void Input() {
    for (int i = 0; i < MAX_SIZE; i++) {
        for (int j = 0; j < MAX_SIZE; j++) {
            cin >> board[i][j];
        }
    }
}

void Print() {
    for (int i = 0; i < MAX_SIZE; i++) {
        for (int j = 0; j < MAX_SIZE; j++) {
            cout << board[i][j] << " ";
        }
        cout << '\n';
    }
}

bool Promising(int row, int col, int num) {
    // (1) 행/열 체크
    for (int i = 0; i < MAX_SIZE; i++) {
        if (board[row][i] == num) {    // 행 체크 : 같은 행에 동일한 숫자가 있을 경우
            return false;
        }
        if (board[i][col] == num) {    // 열 체크 : 같은 열에 동일한 숫자가 있을 경우
            return false;
        }
    }

    // (2) 3x3 박스 체크
    int startRow = (row / 3) * 3;
    int endRow = (row / 3) * 3 + 3;
    int startCol = (col / 3) * 3;
    int endCol = (col / 3) * 3 + 3;

    for (int i = startRow; i < endRow; i++) {
        for (int j = startCol; j < endCol; j++) {
            if (board[i][j] == num) {
                return false;
            }
        }
    }
    return true;
}

void DFS(int cnt) {
    if (cnt == 81) {
        Print();
        exit(0);    // 반드시 exit(0)으로 처리하여 강제 종료! (return으로 처리할 경우, 통과 불가)
    }

    int row = cnt / 9;    // 행 구하기
    int col = cnt % 9;    // 열 구하기

    if (!board[row][col]) {    // 칸이 채워져 있지 않을 경우
        for (int i = 1; i <= MAX_SIZE; i++) {
            if (Promising(row, col, i)) {
                board[row][col] = i;
                DFS(cnt + 1);
                board[row][col] = 0;    // 백트래킹
            }
        }
    }
    else {    // 칸이 채워져 있을 경우
        DFS(cnt + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    DFS(0);

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [백트래킹]
• 골드IV