[백준] 2580번 스도쿠 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개씩 한 칸씩 띄워서 출력한다.

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

 

접근방법

backtracking으로 구현하였다.

1. 먼저 스도쿠 판에 비어있는 칸 개수를 센다. -> n

2. backtracking 진행

2-1. 가로 세로 3X3 조건에 부합하는 k 가 발견되면 탐색을 진행한다.

2-2. backtracking 진행시 depth가 n+1이 되면 모든 빈칸을 채운 후 정답을 도출함을 의미함으로 이를 result 배열에 담는다.

3. 하나의 정답을 도출한 후 fin변수를 통해 아직 다른 정답을 찾는 중인 함수 콜스택들을 종료시켜 준다.

4. 정답 출력 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n=0;
int b[10][10]={0};
int result[10][10];
int fin=0;
void bt(int depth, int b[][10]){
    if(depth==n+1){
      fin=1;
      for(int i=1; i<=9; i++){
            for(int j=1; j<=9; j++){
                result[i][j] = b[i][j];
            }
        }
        return ;
    }
    
    for(int i=1; i<=9; i++){
        for(int j=1; j<=9; j++){
            if(b[i][j]==0){
                for(int k=1; k<=9; k++){
                    if(fin) return ;
                    b[i][j]=0;
                    //k가 적합하면 k 넣고 back tracking
                    bool pass = true;
                    for(int x=1; x<=9; x++){
                        if(b[x][j]==k || b[i][x]==k){
                          pass = false;
                        }
                    }
                    for(int x=((i-1)/3)*3+1; x<=((i-1)/3)*3+3; x++){
                        for(int y=((j-1)/3)*3+1; y<=((j-1)/3)*3+3; y++){
                            if(b[x][y]==k){
                              pass = false;
                            }
                        }
                    }
                    b[i][j]=k;
                    if(pass) bt(depth+1, b);
                    b[i][j]=0;
                }
                return ;
            }
        }
    }
    return ;
}
int main()
{   
    for(int i=1; i<=9; i++){
        for(int j=1; j<=9; j++){
            scanf("%d", &b[i][j]);
            if(b[i][j]==0) n++;
        }
    }
    bt(1, b);
    for(int i=1; i<=9; i++){
            for(int j=1; j<=9; j++){
                printf("%d ", result[i][j]);
            }
            printf("\n");
        }
}

느낀점

3X3 조건을 만족하는지를 확인할때 꼼꼼이 따지지 않고 범위를 정했다가 1~3범위를 0~2범위로 착각하여 디버깅 시간이 오래 걸렸다. 더 꼼꼼하게 생각하고 코딩해야 겠다.