[백준 2580] 스도쿠

스도쿠 문제이다.

주어진 스도쿠를 3가지 조건을 만족하여

다양한 경우의 수 중에서 하나만 출력하면 된다.

조건1 : 각각의 가로 줄에는 1 ~ 9 숫자 하나씩만 가능하다.

조건2 : 각각의 세로 줄에는 1 ~ 9 숫자 하나씩만 가능하다.

조건3 : 작은 3*3 사각형에는 1 ~ 9 숫자 하나씩만 가능하다.

나의 경우에는 bool check1, 2, 3을 사용하여 구현하였으며

int sudoku[9][9];                    // 기존의 스도쿠 배열

vector<pair<int, int> > list;        // 비어있는 스도쿠 배열

list의 x와 y를 활용하여, 1부터 9까지 순회시켜

조건 1,2,3에 부합할 경우 다음 깊이로 진행한다. (DFS 탐색)

모든 깊이를 탐색할 시

다양한 경우의 수가 나오기 때문에

(문제에서 제시한 답은 경우의 수 1개)

강제로 종료시킨다.

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

문제

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

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

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

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

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

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

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

입력

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

출력

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

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

예제 입력 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

소스코드

#include<iostream>
#include<vector>
#include<utility>
 
using namespace std;
 
int sudoku[9][9];
vector<pair<int, int> > list;
 
// sudoku 배열에 삽입
// 비어있는 스도쿠 배열은 vector list에 삽입 
void insert(){
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            int tmp;
            cin >> tmp;
            sudoku[i][j] = tmp;
            if(tmp == 0)
                list.push_back(make_pair(i,j));
        }
    }
}
 
// 가로 검사  
bool check1(int r, int num){
    for(int i = 0; i < 9; i++){
        if(sudoku[r][i] == num)
            return false;
    }
    return true;
}
 
// 세로 검사  
bool check2(int c, int num){
    for(int i = 0; i < 9; i++){
        if(sudoku[i][c] == num)
            return false;
    }
    return true;
}
 
// 3x3 검사  
bool check3(int r, int c, int num){
    r = r / 3;
    c = c / 3;
    for(int rr = r * 3; rr < (r * 3) + 3;  rr++){
        for(int cc = c * 3; cc < (c * 3) + 3; cc++){
            if(sudoku[rr][cc] == num)
                return false;
        }
    }
    return true;
}
bool pass(int x, int y, int num){
    return (check1(x,num) && check2(y,num) && check3(x,y,num))? true : false;
}
 
// dfs 탐색을 사용하여 비어있는 스도쿠 공간을 채운다.
void dfs(int index){
    if(index == list.size()){                                    // 이미 비어있는 모든 공간을 채운 상태 
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++)
                cout << sudoku[i][j] << ' ';
            cout << '\n';
        }
        exit(0);                                                // 강제 종료 
    }
    
    for(int i = 1; i <= 9; i++){                                // 1부터 9까지 삽입해본다. 
        int x = list[index].first;                                // 가로 
        int y = list[index].second;                                // 세로  
        if(pass(x,y,i)){        // 스도쿠 조건에 만족하면  
            sudoku[x][y] = i;                                    // sudoku 배열에 삽입     
            dfs(index+1);                                        // 비어있는 다음 스도쿠 배열을 탐색 
            sudoku[x][y] = 0;                                    // 위에서 스도쿠 조건 만족에 실패하여 다시 빠져나옴 
        }
    }
}
int main(void){
    insert();                                                    // 기존의 스도쿠 배열 삽입 
    dfs(0);                                                        // dfs 탐색 
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.