[C++ 백준 풀이][Gold IV] 2239번, 2580번 : 스도쿠 (백트래킹)

이 포스트는 프로그래밍 문제 풀이 사이트 백준 Online Judge의 2239번 : 스도쿠와 2580번 : 스도쿠, 4056번 : 스-스-스도쿠 문제에 대한 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Gold IV에 해당하며, 이 문제를 풀기 위해 필요한 배경지식인 백트래킹 개념에 대해 다룰 것입니다.

 

참고로 2239번 문제와 2580번 문제는 거의 동일한 문제로, 입출력 부분만 약간 수정해주면 똑같이 풀이할 수 있습니다.

 

 

2239번 : 스도쿠

 

9개의 줄에 9개의 숫자로 스도쿠 판이 입력되었을 때, 스도쿠를 풀이하여 답을 출력하면 되는 문제입니다.

빈칸은 0으로 입력되며, 각 박스는 3×3 크기로 스도쿠의 규칙을 알아야 풀 수 있는 문제입니다.

 

 

↓ 위의 이미지와 동일한 복사 가능한 풀이 코드는 아래의 접은 글에 정리되어 있으니 참고해주세요.

#include <iostream>
using namespace std;

int board[10][10];
bool given[10][10] = {0, }, row[10][10] = {0, }, col[10][10] = {0, }, box[10][10] = {0, }, check;

void solve(int i, int j, int dir) {
    if(given[i][j]) {
        if(dir == 1) {
            if(j < 9) solve(i, j+1, 1);
            else if(j == 9 && i < 9) solve(i+1, 1, 1);
            else if(j == 9 && i == 9) return;
        }
        else if(dir == -1) {
            if(j > 1) solve(i, j-1, -1);
            else if(j == 1 && i > 1) solve(i-1, 9, -1);
            else if(j == 1 && i == 1) return;
        }
    }
    else if(!given[i][j]) {
        check = 0;
        row[i][board[i][j]] = 0;
        col[j][board[i][j]] = 0;
        box[((i-1)/3)*3+(j-1)/3+1][board[i][j]] = 0;
        for(int k=board[i][j]+1; k<=9; k++) {
            if(!row[i][k] && !col[j][k] && !box[((i-1)/3)*3+(j-1)/3+1][k]) {
                board[i][j] = k;
                row[i][k] = 1;
                col[j][k] = 1;
                box[((i-1)/3)*3+(j-1)/3+1][k] = 1;
                check = 1;
                break;
            }
        }
        if(check) {
            if(j < 9) solve(i, j+1, 1);
            else if(j == 9 && i < 9) solve(i+1, 1, 1);
            else if(j == 9 && i == 9) return;
        }
        else if(!check) {
            if(board[i][j]) {
                row[i][board[i][j]] = 0;
                col[j][board[i][j]] = 0;
                box[((i-1)/3)*3+(j-1)/3+1][board[i][j]] = 0;
                board[i][j] = 0;
            }
            if(j > 1) solve(i, j-1, -1);
            else if(j == 1 && i > 1) solve(i-1, 9, -1);
            else if(j == 1 && i == 1) return;
        }
    }
}

int main() {
    for(int i=1; i<=9; i++)
        for(int j=1; j<=9; j++) {
            scanf("%1d", &board[i][j]);
            if(board[i][j]) {
                given[i][j] = 1;
                row[i][board[i][j]] = 1;
                col[j][board[i][j]] = 1;
                box[((i-1)/3)*3+(j-1)/3+1][board[i][j]] = 1;
            }
        }
    solve(1, 1, 1);
    for(int i=1; i<=9; i++) {
        for(int j=1; j<=9; j++) cout << board[i][j];
        cout << "\n";
    }
}

 

풀이 코드가 예상치 못하게 조금 길어졌는데, 결론적으로는 각 줄과 박스에 들어있는 숫자를 검사하여 백트래킹으로 해결하는 문제였습니다.

생각보다 채점 시간이 넉넉해서 백트래킹 코드를 작성할 줄 알기만 하면 해결이 가능했습니다.

숫자를 검사하는 방법은, 저의 경우에는 row, col, box 배열을 따로 만들어서 row[i][j]의 경우 i번째 행에 숫자 j가 존재하는지 여부를 검사하는 용도로 사용하였습니다.

배열의 값이 1이면 j가 존재하는 것이고, 0이면 존재하지 않음을 알 수 있습니다.

 

위의 코드에서 solve 함수가 백트래킹을 수행하는 함수에 해당합니다.

검사 방향의 dir를 선언해서 dir가 1이면 다음 행 다음 열을 검사하는 것이고, dir가 -1이면 이미 입력한 숫자를 지우면서 앞의 숫자를 고치는 것입니다.

 

1행 1열부터 빈칸을 찾고, 빈칸이 나오면 1부터 대입을 하면서 같은 행, 열, 박스에 같은 숫자가 없을 때 대입을 하고 다음 칸으로 넘어갑니다.

만약 1~9를 모두 검사했는데도 대입 가능한 숫자가 없는 경우에는 현재 칸의 정보들을 지우면서 앞 칸으로 넘어가서 앞 칸의 대입 가능한 다른 숫자를 검사합니다.

 

 

위의 풀이 코드를 제출해보면 160ms라는 짧지는 않은 시간에 문제가 해결됨을 알 수 있습니다.

 

 

2580번 : 스도쿠

 

이 문제 역시 위의 문제와 동일하게 스도쿠를 풀이하도록 작성하면 됩니다.

다만 입출력 부분에서 공백이 한 칸씩 추가되기 때문에 동일한 코드를 제출하되, 입출력에서 공백만 처리하도록 고쳐주면 됩니다.

 

 

제출해보면 위의 문제보다 더 짧은 시간에 채점이 완료됨을 알 수 있습니다.