[백준] 2239 스도쿠 (C++)

링크

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

 

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

---

풀이

백트래킹으로 모든 경우의 수를 조회하면 되는 문제이다.

주의해야할 점은 답이 여러 개일 수 있고 답은 그 중 가장 작은 수를 출력해야 하므로

좌표가 (y, x)일 때 (1,1), (1,2), ... (1, 9), (2, 1) ... (9, 9) 순서대로 조회해야 하고

수를 1부터 9까지 차례대로 대입해야 한다는 것이다.

 

코드

#include <iostream>
using namespace std;

int sudoku[10][10];
bool findAnswer = false;

// 스도쿠의 조건을 만족하는지를 검사하는 함수
bool checkValue(int v, int y, int x){
    // 가로 방향 체크
    for (int c = 1; c <= 9; c++){
        if (sudoku[y][c] == v){
            return false;
        }
    }
    // 세로 방향 체크
    for (int r = 1; r <= 9; r++){
        if (sudoku[r][x] == v){
            return false;
        }
    }
    // 3×3 사각형 체크
    int yStart, yEnd, xStart, xEnd;
    if (y <= 3){
        yStart = 1;
        yEnd = 3;
    }
    else if (y <= 6){
        yStart = 4;
        yEnd = 6;
    }
    else{
        yStart = 7;
        yEnd = 9; 
    }
    if (x <= 3){
        xStart = 1;
        xEnd = 3;
    }
    else if (x <= 6){
        xStart = 4;
        xEnd = 6;
    }
    else{
        xStart = 7;
        xEnd = 9;
    }
    for (int r = yStart; r <= yEnd; r++){
        for (int c = xStart; c <= xEnd; c++){
            if (sudoku[r][c] == v){
                return false;
            }
        }
    }
    // 위 조건들을 모두 통과했다면 true 리턴
    return true;
}

// 재귀로 백트래킹을 구현
void solve(int y, int x){
    // y가 10, x가 1이거나 이미 정답을 찾았다면 탐색 종료
    if ((y == 10 && x == 1) || findAnswer){
        findAnswer = true;
        return;
    }
    // 사전식으로 앞서는 것을 출력해야 함에 유의
    // 스도쿠가 이미 채워져 있다면 다음을 탐색
    if (sudoku[y][x] > 0){
        if (x == 9){
            solve(y+1, 1);
        }
        else{
            solve(y, x+1);
        }
    }
    // 스도구카 채워져 있지 않다면 1~9까지 차례대로 대입
    else{
        for (int trg = 1; trg <= 9; trg++){
            if (checkValue(trg, y, x)){
                sudoku[y][x] = trg;
                if (x == 9){
                    solve(y+1, 1);
                }
                else{
                    solve(y, x+1);
                }
                if (findAnswer){
                    return;
                }
                sudoku[y][x] = 0;
            }
        }
    }
}

int main(){
    for (int i = 1; i <= 9; i++){
        string input;
        cin >> input;
        for (int j = 1; j <= 9; j++){
            sudoku[i][j] = input[j-1]-'0';
        }
    }

    solve(1, 1);

    for (int i = 1; i <= 9; i++){
        for (int j = 1; j <= 9; j++){
            cout << sudoku[i][j];
        }
        cout << "\n";
    }
}