파이썬으로 유효한 스도쿠 보드 검증하기

9×9 크기의 스도쿠 보드가 주어졌을 때, 그 보드가 유효한지 판별하는 문제를 살펴보겠습니다. 이때 검증 대상은 실제로 숫자가 채워진 칸뿐이며, 다음 세 가지 규칙을 모두 만족해야 합니다.

• 각 행에는 1부터 9까지의 숫자가 중복 없이 포함되어야 합니다.
• 각 열에는 1부터 9까지의 숫자가 중복 없이 포함되어야 합니다.
• 격자를 나눈 9개의 3×3 서브 박스 각각에도 1부터 9까지의 숫자가 중복 없이 포함되어야 합니다.

예를 들어 다음과 같은 스도쿠 격자가 주어졌다고 가정해 봅시다.

위 보드는 세 가지 규칙을 모두 만족하므로 유효한 보드입니다.

문제 해결 접근 방식

이 문제는 보드를 한 번만 순회하면서 행, 열, 3×3 박스를 동시에 검사하는 방식으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

• i를 0부터 8까지 반복합니다.
  • 행(row), 열(column), 박스(block)를 기록할 빈 딕셔너리를 준비하고, row_cube := 3 × (i // 3), column_cube := 3 × (i % 3)으로 초기화합니다.
  • j를 0부터 8까지 반복합니다.
    • board[i][j]가 빈 칸('.')이 아니면서 이미 row 딕셔너리에 존재하면 False를 반환합니다.
    • row[board[i][j]] := 1로 기록합니다.
    • board[j][i]가 빈 칸이 아니면서 이미 column 딕셔너리에 존재하면 False를 반환합니다.
    • column[board[j][i]] := 1로 기록합니다.
    • rc := row_cube + j // 3, cc := column_cube + j % 3으로 현재 검사 중인 3×3 박스 안의 좌표를 계산합니다.
    • board[rc][cc]가 빈 칸이 아니면서 이미 block 딕셔너리에 존재하면 False를 반환합니다.
    • block[board[rc][cc]] := 1로 기록합니다.
• 모든 검사를 통과하면 True를 반환합니다.

스도쿠 보드의 크기는 9×9로 고정되어 있으므로 이 알고리즘의 시간 복잡도는 사실상 상수인 O(1)이며, 전체 81개 칸에 대해 각각 상수 시간의 검사만 수행됩니다.

파이썬 구현 예제

아래 코드를 통해 구현 방법을 더 자세히 이해해 보겠습니다.

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        for i in range(9):
            row = {}
            column = {}
            block = {}
            row_cube = 3 * (i//3)
            column_cube = 3 * (i%3)
            for j in range(9):
                if board[i][j] != '.' and board[i][j] in row:
                    return False
                row[board[i][j]] = 1
                if board[j][i] != '.' and board[j][i] in column:
                    return False
                column[board[j][i]] = 1
                rc = row_cube + j//3
                cc = column_cube + j%3
                if board[rc][cc] in block and board[rc][cc] != '.':
                    return False
                block[board[rc][cc]] = 1
        return True

ob1 = Solution()
print(ob1.isValidSudoku([
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]]))

입력

[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

출력

true