스도쿠 그리드 유효성 검사 문제란?
9×9 크기의 스도쿠 보드가 주어졌을 때, 해당 그리드가 유효한(valid) 스도쿠인지 판별하는 프로그램을 파이썬으로 작성해 보겠습니다. 여기서 중요한 점은 빈 칸은 무시하고, 숫자가 채워진 셀만 아래 규칙에 따라 검증하면 된다는 것입니다.
유효성 검사의 세 가지 기본 규칙
- 각 행(row)에는 1부터 9까지의 숫자가 중복 없이 한 번씩만 나타나야 합니다.
- 각 열(column)에는 1부터 9까지의 숫자가 중복 없이 한 번씩만 나타나야 합니다.
- 그리드를 이루는 9개의 3×3 서브 박스(sub-box) 각각에도 1부터 9까지의 숫자가 중복 없이 나타나야 합니다.
예를 들어 아래와 같은 스도쿠 그리드가 주어졌다고 가정해 봅시다.
이 그리드는 위 세 가지 규칙을 모두 만족하므로 유효한(valid) 스도쿠입니다.
해결 접근 방식
핵심 아이디어는 각 행, 열, 3×3 블록마다 이미 등장한 숫자를 추적하는 것입니다. 딕셔너리(해시)를 활용하면 중복 여부를 O(1) 시간에 확인할 수 있습니다. 알고리즘 단계는 다음과 같습니다.
- i를 0부터 8까지 반복합니다.
- 행(row), 열(column), 블록(block) 검사용 빈 딕셔너리를 매번 새로 생성합니다.
- 현재 i가 속한 3×3 블록의 시작 위치를 계산합니다. 즉, row_cube = 3 × (i // 3), col_cube = 3 × (i % 3) 입니다.
- j를 0부터 8까지 반복하며 다음을 수행합니다.
- board[i][j]가 빈 칸('.')이 아니면서 이미 row 딕셔너리에 있다면 → False 반환 (행 중복).
- 그렇지 않으면 board[i][j]를 row 딕셔너리에 기록합니다.
- board[j][i]가 빈 칸이 아니면서 column 딕셔너리에 이미 있다면 → False 반환 (열 중복).
- 그렇지 않으면 board[j][i]를 column 딕셔너리에 기록합니다.
- 블록 내부 좌표를 계산합니다: rc = row_cube + j // 3, cc = col_cube + j % 3.
- board[rc][cc]가 빈 칸이 아니면서 block 딕셔너리에 이미 있다면 → False 반환 (3×3 블록 중복).
- 그렇지 않으면 board[rc][cc]를 block 딕셔너리에 기록합니다.
- 모든 반복을 통과하면 True를 반환합니다.
여기서 재미있는 포인트는 단 하나의 이중 반복문으로 행·열·블록 검사를 동시에 처리한다는 점입니다. 바깥 루프의 인덱스 i는 '검사 대상 행', '검사 대상 열', 그리고 '검사 대상 블록'의 번호로 삼중 역할을 하기 때문입니다.
파이썬 구현 코드
아래는 위 알고리즘을 실제로 구현한 코드입니다.
class Solution(object):
def isValidSudoku(self, board):
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
정리 및 시간 복잡도
이 알고리즘은 9×9 고정 크기 그리드를 두 번의 중첩 루프로 훑기 때문에 시간 복잡도는 O(81), 즉 상수 시간 O(1)로 볼 수 있으며, 공간 복잡도 역시 각 루프마다 최대 9개의 키만 저장하는 세 개의 딕셔너리를 사용하므로 O(1)입니다.
주의할 점은 이 코드가 스도쿠가 풀이 가능한지(solvable)를 판별하는 것이 아니라, 현재 채워진 숫자들이 규칙에 맞게 배치되어 있는지(유효한 상태인지)를 검사한다는 것입니다. 빈 칸('.')은 어떤 숫자든 들어갈 수 있는 후보로 취급되어 검증에서 제외됩니다. 만약 실제로 스도쿠를 풀어내는 솔버(solver)가 필요하다면 백트래킹(backtracking) 기법을 추가로 구현해야 합니다.