[백준 / 2239 / Python] 스도쿠

문제 요약

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 최적화가 극적으로 효과를 발휘합니다.

---

참고

• 백준 2239번 문제 링크
• 백트래킹 위키백과
• PyPy 공식 사이트

---