Algorithm/백준
[백준 / 2239 / Python] 스도쿠
Kun Woo Kim
2025. 6. 13. 23:24
반응형
문제 요약
9×9 크기의 스도쿠 보드가 주어집니다.
각 행, 각 열, 그리고 3×3 박스마다 1~9가 중복 없이 한 번씩만 등장해야 합니다.
아직 채워지지 않은 칸은 0으로 주어지며,
모든 빈 칸을 조건에 맞게 채운 "가장 사전순으로 앞서는" 해답을 출력하는 문제입니다.
접근 방식
이 문제는 대표적인 "백트래킹" 유형입니다.
- 먼저, 빈 칸(0)의 좌표를 모두 저장합니다.
- 각 빈 칸에 대해 1~9 중 가능한 숫자를 하나씩 시도합니다.
- 숫자를 넣었을 때 행, 열, 3×3 박스에 중복이 없으면 다음 칸으로 진행합니다.
- 만약 모든 빈 칸을 채웠다면, 그 즉시 답을 출력하고 탐색을 종료합니다(사전순 보장).
- 불가능하면 백트래킹(원상복구)하여 다른 숫자를 시도합니다.
실생활 비유로 설명하면,
"빈 칸마다 1~9 중 가능한 숫자를 하나씩 넣어보며,
규칙에 어긋나면 바로 되돌아가고,
모든 칸을 채우면 바로 답을 내는"
체계적인 시도와 되돌리기(백트래킹) 전략입니다.
코드 구현
아래는 Python으로 구현한 코드입니다.
import sys
input = sys.stdin.readline
board = [list(map(int, list(input().strip()))) for _ in range(9)]
zeros = [(i, j) for i in range(9) for j in range(9) if board[i][j] == 0]
finished = False
def is_valid(x, y, num):
# 행 검사
for i in range(9):
if board[x][i] == num:
return False
# 열 검사
for i in range(9):
if board[i][y] == num:
return False
# 3x3 박스 검사
box_x = (x // 3) * 3
box_y = (y // 3) * 3
for i in range(3):
for j in range(3):
if board[box_x + i][box_y + j] == num:
return False
return True
def dfs(index):
global finished
if finished:
return
if index == len(zeros):
for row in board:
print("".join(map(str, row)))
finished = True
return
x, y = zeros[index]
for num in range(1, 10): # 1~9
if is_valid(x, y, num):
board[x][y] = num
dfs(index + 1)
board[x][y] = 0
dfs(0)시간복잡도 & 최적화
- 시간복잡도:
- 최악의 경우, 빈 칸이 많으면 9^빈칸수 만큼의 경우의 수가 생깁니다.
- 하지만, 조건 위반 시 즉시 백트래킹하므로 실제 탐색 분기는 훨씬 적어집니다.
- 최적화 포인트:
- 가능한 숫자를 빠르게 거르는 is_valid 함수
- 답을 찾으면 바로 종료하는 finished 플래그
느낀 점 / 팁
- 스도쿠처럼 "모든 경우를 시도"해야 하는 문제는 백트래킹이 정석입니다.
- 사전순 출력을 위해, 빈 칸을 순서대로 채우고, 숫자도 1부터 차례로 시도합니다.
- 파이썬의 재귀 깊이와 실행 속도에 주의해야 하며,
PyPy3로 제출하면 훨씬 빠르게 동작합니다.
python3로 풀면 시간초과가 나오고, pypy3로 제출하면 성공한다! 왜 그럴까?
- PyPy3는 파이썬 코드를 JIT(Just-In-Time) 컴파일로 빠르게 실행합니다.
특히, 반복문과 재귀가 많은 백트래킹 문제에서 큰 차이가 납니다. - Python3(CPython)은 인터프리터 방식이라,
같은 코드라도 실행 속도가 PyPy3에 비해 훨씬 느립니다. - 이 문제처럼 "수많은 재귀 호출과 조건 검사"가 반복되는 경우,
PyPy3의 JIT 최적화가 극적으로 효과를 발휘합니다.
참고
반응형