(파이썬) 백준 2580번 "스도쿠"

---

# 답

import sys

board = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
zero = []

for y in range(9):
    for x in range(9):
        if not board[y][x]:
            zero.append((y, x))

def is_sudoku(ty, tx, n):
    y = (ty // 3) * 3
    x = (tx // 3) * 3
    for i in range(9):
        # 가로줄 확인
        if board[ty][i] == n:
            return False
        # 세로줄 확인
        if board[i][tx] == n:
            return False
        # 3 * 3 확인
        if board[y + i // 3][x + i % 3] == n:
            return False
    return True

def dfs(idx):
    if idx == len(zero):
        for y in range(9):
            print(*board[y])
        exit(0)

    y, x = zero[idx]
    for i in range(1, 10):
        if is_sudoku(y, x, i):
            board[y][x] = i
            dfs(idx + 1)
            board[y][x] = 0

dfs(0)

※ PyPy3로 제출해야 시간초과가 나지 않는 코드입니다.

 

 

 

 

---

# 풀이과정

 

1) 빈 칸 좌표만 따로 모아서 zero라는 리스트에 담는다.

2) zero에 있는 좌표들을 하나씩 탐색한다. (현재 탐색 중인 좌표를 y, x라고 하겠다.)

3) 좌표 (y, x)에 1부터 9까지의 숫자들을 하나씩 넣어본다.

4) 좌표 (y, x)에 숫자 n을 넣었을 때 스도쿠 조건을 만족한다면, 다음 빈 칸을 탐색한다.

5) 재귀 호출을 이용해 2) ~ 4) 반복

6) 모든 빈 칸에 숫자를 대입하는데 성공했다면(idx == len(zero)), 정답을 출력하고 프로그램을 종료한다.

 

 

dfs와 백트래킹이 쓰인 문제입니다. 특별히 어려운 개념이 쓰이진 않았지만 헤매기 쉬운 문제예요. 예전에 C++로 풀 때는 시간초과 안 나고 무사히 통과했던 코드를 파이썬으로 그대로 구현했는데 시간초과가 나더라구요. 근데 또 그 코드를 그대로 PyPy3로 제출하면 무사히 통과하네요..