LeetCode 37번 Sodoku Solver

https://leetcode.com/problems/sudoku-solver/

---

문제 파악

스도쿠는 모든 행, 열, 3x3 박스에서 1~9의 숫자가 모두 들어가야 한다. 그렇기 때문에 백트래킹을 통해서 행에 대해서, 열에 대해서, 마지막으로 박스에 대해서 스도쿠의 법칙을 만족하는지 탐색해야 한다.

접근 방법

백트래킹을 통해서 구현하고자 한다. 빈 셀에 가능한 숫자를 하나씩 넣어가면서 조건을 만족하는지 확인한다. 조건을 만족하면 다음 빈 셀로 넘어가고 조건을 만족하지 않으면 그 숫자를 빼고 다른 숫자를 시도한다. 만약 모든 숫자를 시도해도 조건을 만족하지 않으면 이전 셀로 돌아가서 다른 숫자를 시도한다 (백트래킹).

코드 구현

from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        # 유효한지 확인하기
        def is_valid(board: List[List[str]], row: int, col: int, num: str) -> bool:
            # 열이나 행에 이미 숫자가 있는지 확인하기
            for i in range(9):
                if board[row][i] == num:
                    return False  # 숫자가 현재 행에 이미 있음
                if board[i][col] == num:
                    return False  # 숫자가 현재 열에 이미 있음

            # 3x3 박스도 확인
            start_row = 3 * (row // 3)
            start_col = 3 * (col // 3)
            for i in range(3):
                for j in range(3):
                    if board[start_row + i][start_col + j] == num:
                        return False  # 숫자가 3x3 박스에 이미 있음

            return True

        def backtrack(board: List[List[str]]) -> bool:
            for row in range(9):
                for col in range(9):
                    if board[row][col] == '.': # 빈 셀 찾기
                        for num in '123456789':
                            if is_valid(board, row, col, num): # 빈 셀에 각 숫자를 넣을 수 있을지 시도
                                board[row][col] = num # True를 호출하면 만족한 것이므로 숫자를 배치
                                if backtrack(board):
                                    return True
                                board[row][col] = '.'
                        return False
            return True

        backtrack(board)

주어진 board를 직접 수정해야 하므로, 수정된 보드가 조건을 만족하는지 확인한다.

is_valid 함수는 숫자를 특정 위치에 놓았을 때 그 숫자가 유효한지 판단한다.

backtrack 함수는 백트래킹을 수행하여 가능한 해를 찾는다.

배우게 된 점

유효성을 확인하는 함수를 통해서 효율적으로 백트래킹을 할 수 있다. 그 외에는 문제 자체가 좀 어렵다고 느껴서 많이 풀어보고 많은 것을 얻어가야 할 것 같다.