[백준/C++] 2580 번 : 스도쿠 풀이

백준 2580 번 : 스도쿠

문제 링크 : 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개씩 한 칸씩 띄워서 출력한다.

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

 

제한

baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.

• C++14: 80ms
• Java: 292ms
• PyPy3: 1172ms

---

풀이1 (오류)

#include <iostream>

using namespace std;

int sudoku[10][10];

bool check_row[10][10]; // 행 검사 : x행에 숫자 y가 있으면 true
bool check_col[10][10]; // 열 검사 : x열에 숫자 y가 있으면 true
bool check_square[10][10]; // 작은 정사각형 검사 : x번째 작은 정사각형에 숫자 y가 있으면 true

// row행 col열이 속하는 작은 정사각형 구하기
int get_square(int row, int col){
    return (row/3)*3 + (col/3);
}

// sudoku 출력
void print(){
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cout << sudoku[i][j] << ' ';
        }
        cout << '\n';
    }
}

// num번째 스도쿠 구하기
void solve(int num){
    // 마지막 칸인 경우 -> 출력 후 종료
    if(num == 81) {
        print();
        return;
    }
    
    // 행, 열 구하기
    int x = num/9; int y = num%9;
    
    if(sudoku[x][y] != 0){
        // 수가 있으면 -> 다음 수로 넘어가기
        solve(num+1);
    } else {
        // 수가 없으면 -> 1~9 검사해서 수 채우기
        for(int i=1; i<=9; i++){
            if(!check_row[x][i] && !check_col[y][i] && !check_square[get_square(x, y)][i]){
                // 스도쿠 처리
                check_row[x][i] = true;
                check_col[y][i] = true;
                check_square[get_square(x, y)][i] = true;
                sudoku[x][y] = i;
                
                solve(num+1);
                
                // 다시 돌려놓기 (백트래킹)
                check_row[x][i] = false;
                check_col[y][i] = false;
                check_square[get_square(x, y)][i] = false;
                sudoku[x][y] = 0;
            }
        }
    }
}

int main(void){
    
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cin >> sudoku[i][j];
            
            // 빈칸이 아닌 경우 처리
            if(sudoku[i][j] != 0){
                check_row[i][sudoku[i][j]] = true;
                check_col[j][sudoku[i][j]] = true;
                check_square[get_square(i, j)][sudoku[i][j]] = true;
            }
        }
    }
    
    // 0번 칸부터 채우기 시작
    solve(0);
    
    return 0;
}

틀렸습니다! ^^

스도쿠 빈 칸에 알맞은 숫자를 넣으려면 세 가지 조건을 충족해야 한다.

1. 빈 칸의 행에 겹치는 숫자가 존재하면 안 된다.
2. 빈 칸의 열에 겹치는 숫자가 존재하면 안 된다.
3. 빈 칸의 작은 정사각형 내에 겹치는 숫자가 존재하면 안 된다.

각각 배열 check_row, check_col, check_square 로 검사했다. 그러나 제출하니 오류가 나왔다 ㅠㅠ (사실 아직 정확한 이유는 모르겠다.)

 

풀이 2

#include <iostream>

using namespace std;

int sudoku[10][10];

bool check_row[10][10]; // 행 검사 : x행에 숫자 y가 있으면 true
bool check_col[10][10]; // 열 검사 : x열에 숫자 y가 있으면 true
bool check_square[10][10]; // 작은 정사각형 검사 : x번째 작은 정사각형에 숫자 y가 있으면 true

// row행 col열이 속하는 작은 정사각형 구하기
int get_square(int row, int col){
    return (row/3)*3 + (col/3);
}

// sudoku 출력
void print(){
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cout << sudoku[i][j] << ' ';
        }
        cout << '\n';
    }
}

// num번째 스도쿠 구하기
bool solve(int num){
    // 마지막 칸인 경우 -> 출력 후 종료
    if(num == 81) {
        print();
        return true;
    }
    
    // 행, 열 구하기
    int x = num/9; int y = num%9;
    
    if(sudoku[x][y] != 0){
        // 수가 있으면 -> 다음 수로 넘어가기
        return solve(num+1);
    } else {
        // 수가 없으면 -> 1~9 검사해서 수 채우기
        for(int i=1; i<=9; i++){
            if(!check_row[x][i] && !check_col[y][i] && !check_square[get_square(x, y)][i]){
                // 스도쿠 처리
                check_row[x][i] = true;
                check_col[y][i] = true;
                check_square[get_square(x, y)][i] = true;
                sudoku[x][y] = i;
                
                if(solve(num+1)){
                    return true;
                }
                
                // 다시 돌려놓기 (백트래킹)
                check_row[x][i] = false;
                check_col[y][i] = false;
                check_square[get_square(x, y)][i] = false;
                sudoku[x][y] = 0;
            }
        }
    }
    
    return false;
}

int main(void){
    
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cin >> sudoku[i][j];
            
            // 빈칸이 아닌 경우 처리
            if(sudoku[i][j] != 0){
                check_row[i][sudoku[i][j]] = true;
                check_col[j][sudoku[i][j]] = true;
                check_square[get_square(i, j)][sudoku[i][j]] = true;
            }
        }
    }
    
    // 0번 칸부터 채우기 시작
    solve(0);
    return 0;
}

0번째 칸부터 탐색을 시작하는 solve 함수에 리턴값을 부여했다. 마지막 칸인 경우 (모든 빈칸을 다 채웠을 경우) 프린트 하도록 했다. 다음 칸을 탐색할 때는 앞선 풀이와는 다르게 리턴값이 true 일 경우에만 재귀함수를 호출하도록 했다.

 

결과는 성공!!

 

풀이 인증