[ 백준 / C++ ] 2239 : 스도쿠

[ 문제 ]

 

2239번: 스도쿠

 

[ 접근방법 ]

 

1행 1열부터 순서대로 숫자를 대입해보고 퍼즐이 완성되면 함수를 종료한다.

 

used 배열을 통해 각 행, 각 열, 각 사각형에 숫자 중복이 없는지 체크한다.

 

used[ 0 ][ i ][ n ] = i 행에 숫자 n이 쓰였는지 여부.

used[ 1 ][ i ][ n ] = i 열에 숫자 n이 쓰였는지 여부.

used[ 2 ][ i ][ n ] = i번째 사각형에 숫자 n이 쓰였는지 여부.

 

[ 소스코드 ]

 

#include <iostream>

using namespace std;

int sudoku[9][9];
bool used[3][9][10];

int getSquareIndex(int x, int y){
    return (x / 3) * 3 + (y / 3);
}

bool solve(int cell){
    if(cell == 81) return true;

    int row = cell / 9, col = cell % 9;

    if(sudoku[row][col]) return solve(cell + 1);

    for(int num = 1; num <= 9; num++){
        if(!used[0][row][num] && !used[1][col][num] && !used[2][getSquareIndex(row, col)][num]){
            used[0][row][num] = used[1][col][num] = used[2][getSquareIndex(row, col)][num] = true;
            sudoku[row][col] = num;

            if(solve(cell + 1)) return true;

            sudoku[row][col] = 0;
            used[0][row][num] = used[1][col][num] = used[2][getSquareIndex(row, col)][num] = false;
        }
    }

    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int i = 0; i < 9; i++){
        string rowInput;
        cin >> rowInput;
        for(int j = 0; j < 9; j++){ 
            sudoku[i][j] = rowInput[j] - '0';
            if(sudoku[i][j]){
                used[0][i][sudoku[i][j]] = used[1][j][sudoku[i][j]] = used[2][getSquareIndex(i, j)][sudoku[i][j]] = true;
            }
        }
    }

    solve(0);

    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){
            cout << sudoku[i][j];
        }
        cout << "\n";
    }

    return 0;
}