[LeetCode # 37] Sudoku Solver

빈 칸이 존재하는 Sudoku 게임판을 보고, Sudoku 규칙에 맞게 빈 칸들을 모두 채우는 문제.

 

이 문제는 Hard 난이도지만, 간단하게 DFS 방식으로 문제 해결이 가능했다. 우선, 빈 칸들의 위치를 찾아 Vector 에 저장하고 각 위치들에 숫자를 1~9 까지 하나씩 넣어 가며 모든 빈 칸들을 채운다. 끝까지 채워진 게 확인되면 실행을 종료하도록 한다.

 

이러한 풀이로 작성한 코드는 다음과 같다.

 

struct _POINT {
    int y, x;
};

class Solution {
public:
    vector<_POINT> vp;
    bool check(vector<vector<char>>& board, _POINT loc, int num) {
        int y = loc.y, x = loc.x;
        // 가로
        for (int j = 0; j<9; j++){
            if (board[y][j] - '0' == num){
                return false;
            }
        }
        // 세로
        for (int i = 0; i<9; i++){
            if (board[i][x] - '0' == num){
                return false;
            }
        }
        // 블락
        for (int i = 0; i<3; i++){
            for (int j = 0; j<3; j++){
                if (board[(y / 3) * 3 + i][(x / 3) * 3 + j] - '0' == num){
                    return false;
                }
            }
        }
        return true;
    }

    int dfs(vector<vector<char>>& board, int idx) {
        if (idx == vp.size())
            return 1;

        for (int num = 1; num <= 9; num++) {
            if (check(board, vp[idx], num)){
                board[vp[idx].y][vp[idx].x] = num + '0';
                int res = dfs(board, idx + 1);
                if (res == 1)
                    return 1;
            }
        }
        board[vp[idx].y][vp[idx].x] = '.';
        return 0;
    }

    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i<9; i++){
            for (int j = 0; j<9; j++){
                if (board[i][j] == '.'){
                    vp.push_back({i, j});
                }
            }
        }
        dfs(board, 0);
    }
};