[백준] 스도쿠

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

2580번: 스도쿠

문제부터 간단하게 요약하면,

 

빈칸이 있는 스도쿠 판이 주어지면, 해당하는 스도쿠 판을 채워서 출력해야 하는 것이 문제입니다.

 

<Solution>

네모난 박스 9칸과, 가로9줄, 세로 9줄을 기록하는 array를 만들어 dfs를 진행합니다. 이 때, 표의 0,0부터 9,9를 각각 0부터 80까지 매핑을 시켜서 나눗셈 연산과, 나머지 연산을 통해 몇번 박스에 속하는지 조금 더 빠르게 연산할 수 있도록 하였습니다. 

 

자세한 내용은 코드를 참고하길 바랍니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>
using namespace std;

#define MAXN (9)
int sudoku[MAXN][MAXN];
int empty_[MAXN*MAXN];
int empty_cnt;

int boxes[9][10];
int rows[9][10];
int columns[9][10];

void InputData(){
    for (int r=0; r<MAXN; r++){
        for (int c=0; c<MAXN; c++){
            cin >> sudoku[r][c];
        }
    }
}
void OutputData(){
    for (int r=0; r<MAXN; r++){
        for (int c=0; c<MAXN; c++){
            cout << sudoku[r][c] << " ";
        }
        cout << endl;
    }
}
bool dfs(int num){ // 현재까지 채운수이자 채워야할 index임
    if(num>= empty_cnt){
        return true;
    }

    int tmp = empty_[num];
    // find which box
    int box_num = (tmp/9)/3 *3 + (tmp%9)/3;
    int row = tmp/9;
    int col = tmp%9;

    // cout << "box_num, row, col : " << box_num << ' ' << row << ' ' << col << endl;

    for(int i = 1; i<=9; i++){
        if(!boxes[box_num][i] && !rows[row][i] && !columns[col][i]){
            sudoku[row][col] = i;
            boxes[box_num][i] = 1;
            rows[row][i] = 1;
            columns[col][i] = 1;
            if(dfs(num+1)){
                return true;
            }
            sudoku[row][col] = 0;
            boxes[box_num][i] = 0;
            rows[row][i] = 0;
            columns[col][i] = 0;
        }
        else{
            continue;
        }
    }
    
    return false;

}

void solution(){
    // find empty place
    for(int r= 0; r<MAXN; r++){
        for(int c= 0; c<MAXN; c++){
            if(sudoku[r][c] == 0) empty_[empty_cnt++] = 9*r+c;
            else{
                //find which box
                int tmp = 9*r+c;
                int box_num = (tmp/9)/3 *3 + (tmp%9)/3;

                boxes[box_num][sudoku[r][c]] = 1;
                rows[r][sudoku[r][c]] = 1;
                columns[c][sudoku[r][c]] = 1;
            }
        }
    }

    dfs(0);


}

int main(){
    InputData();

    solution();

    OutputData();
    return 0;
}