[백준] 2580번 스도쿠 -C/C++

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

2580번: 스도쿠

문제

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

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

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

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

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

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

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

입력

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

출력

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

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

---

    스도쿠는 제한 된 판의 크기에서 유효한 원소들을 집어넣는 작업이기 때문에 백트래킹을 활용하여 일단 원소를 대입해본 뒤 판이 유효한지 검사를 하는 방법을 사용하기로 하였다.

    (0,0) 에서 부터 칸을 채워나간다. 만약 그 자리에 이미 숫자가 있다면 다음 자리로 넘어간다. 해당 자리의 숫자가 0이라면 1~9 까지의 숫자를 각각 대입 해본뒤 유효성 검사를 한다. 유효성 검사는 가로, 세로 , 3*3 격자 칸을 검사하여 중복되는 원소가 있는지 검사하였다. 유효성 검사를 실행하였을때 유효한 판이라고 판단이 된다면 다음 자리로 넘어가서 검사를 진행한다. 만약 끝까지 도달하여 정답을 출력하였다면 flag 를 1로 바꾸어 스택에 쌓여 있는 함수들을 바로 return 할 수 있게 해주었다.

#include <iostream>
#include <cstring>
using namespace std;

int mat[10][10];
bool flag = false;

bool promising(int x, int y){
    int check[10];
    memset(check,0,sizeof(check));
    for(int i = 0 ; i < 9 ; i++){
        if(mat[x][i] && check[mat[x][i]])
            return false;
        check[mat[x][i]]++;
    }
    memset(check,0,sizeof(check));
    for(int i = 0 ; i < 9 ; i++){
        if(mat[i][y] && check[mat[i][y]])
            return false;
        check[mat[i][y]]++;
    }
    x -= x % 3;
    y -= y % 3;
    memset(check,0,sizeof(check));
    for(int i = x; i < x + 3; i++){
        for(int j = y; j < y + 3; j++){
            if(mat[i][j] && check[mat[i][j]])
                return false;
            check[mat[i][j]]++;
        }
    }
    return true;
}

void    solve(int pos){
    if(!flag){
        int x = pos / 9;
        int y = pos % 9;
        if(x == 9 && y == 0){
            for(int i = 0; i < 9 ; i++){
                for(int j = 0 ; j < 9 ; j++)
                    cout << mat[i][j] << " ";
                cout << "\n";
            }
            flag = 1;
            return;
        }
        if(mat[x][y])
            solve(pos + 1);
        else{
            int val = 1;
            while(val < 10){
                mat[x][y] = val;
                if(promising(x,y)){
                    solve(pos + 1);
                }
                mat[x][y] = 0;
                val++;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++)
            cin >> mat[i][j];
    solve(0);
}

---

    코딩 재활 느낌으로 골드 4~5 문제를 풀어보기로 하였다. 스도쿠 문제가 사람들이 많이 푼 문제이길래 풀어보았다. 문제를 보자마자 판을 채워나가는 느낌으로 백트래킹 기법을 사용하면 된다고 판단하였다. 그래서 코드를 작성하였더니 예제에 대한 답이 바로 나왔다! 설레는 마음으로 제출을 눌러봤지만 1%에서 바로 틀렸습니다가 나와버렸다. 이것 저것 살펴보다 보니 답이 나오지 않는 경우가 많았다. 가장 쉬운 예로. 모든 판의 숫자가 0 으로 주어졌을 때 나오지 않았다. 그래서 디버깅을 하던 중 pos를 넘어선 판이 채워져있는 모습을 확인 할 수 있었다. 처음에는 유효하지 않은 판이 유효하다고 나오는 것 같아 promising 함수를 살펴보았지만 문제가 없었고 문제는 판을 채우고 유효하지 않아 함수를 그냥 return 해버릴때 판이 채워져서 유효하지 않은 값이 그냥 들어가 있는 것이 문제였다. 따라서 solve(pos + 1)이 종료되었다는 것은 flag 가 1이 아닌 이상 유효하지 않아 다시 return중이라고 생각하였고 mat[x][y] = 0 이라는 코드를 추가하니 정답을 받을 수 있었다.

     저번학기에는 6전공을 듣다보니 과제에 치여 코딩 문제를 풀지 못했는데 이번 학기는 전공도 적고 학기 말에 코딩 테스트도 봐야하다 보니 방학때 하던 1일 1백준을 다시해야겠다.. 고 마음 먹었으나 쉽사리 되지 않았다. 시작이 반이라고 이제 또 다시 풀기 시작했으니 열심히 해보아야겠다!