[BOJ/백준] 2239번 스도쿠 - Python/파이썬 [해설/풀이]

📌 문제

---

📝 입력

---

💻 출력

---

📖 제한

---

📖 예제 입출력

---

📌 풀이

---

📖 해설

---

DFS를 응용한 BackTracking 문제
문제의 제한사항에 따라 Pypy3로 해결

Python3 에서 시간초과 해결방법
dp의 메모이제이션 기법을 활용하여
각 빈 칸에 들어갈 숫자 후보군을 구하는 시간 최소화

💻 전체코드

---

Pypy3 통과 코드

# Pypy3
import sys
input = sys.stdin.readline

def DFS(depth):
    if depth == len(zeros):     # 모든 빈칸이 채워졌으면
        return True             # return True

    i, j = zeros[depth]
    r, c = (i // 3) * 3, (j // 3) * 3                   # 3 x 3 박스 첫 위치
    candidate1 = set(list(range(1, 10)))                # 숫자 [1 ~ 10]
    candidate2 = set(board[i])                          # 이미 사용된 숫자, 가로
    candidate2 |= set([board[k][j] for k in range(9)])  # 이미 사용된 숫자, 세로
    candidate2 |= set(board[r][c:c + 3])                # 이미 사용된 숫자, 박스 1 2 3
    candidate2 |= set(board[r + 1][c:c + 3])            # 이미 사용된 숫자, 박스 4 5 6
    candidate2 |= set(board[r + 2][c:c + 3])            # 이미 사용된 숫자, 박스 7 8 9
    # sorted(candidate1 - candiate2) = 아직 사용되지 않은 숫자, 사전순 정렬
    for num in sorted(candidate1 - candidate2):     # 현재 빈칸에 들어갈 수 있는 각 숫자에 대해
        board[i][j] = num                           # 일단 넣어보고
        if DFS(depth + 1):                          # 문제가 해결되면
            return True                             # DFS 종료
        board[i][j] = 0                             # 문제가 해결되지 않으면, 0으로 초기화
    return False    # 모든 빈칸을 채울 수 없는 경우, return False

board = [list(map(int, list(input().rstrip()))) for _ in range(9)]
zeros = [(row, col) for row in range(9) for col in range(9) if not board[row][col]]
DFS(0)
for row in board:
    print(*row, sep='')

Python3 통과 코드

# Python3
import sys
input = sys.stdin.readline

def getBlankCandidates(row, col):
    candidates = []                                                 # 현재 row, col 위치에 들어갈 수 있는 숫자 후보군
    for num in range(1, 10):                                        # 1 ~ 9의 각각의 숫자에 대해
        if not dpRow[row][num]:                                     # 스도쿠의 row번째 행에 대하여 사용된 적이 없는 숫자이고
            if not dpCol[col][num]:                                 # 스도쿠의 col번째 열에 대하여 사용된 적이 없는 숫자이고
                if not dpSquare[(row // 3) * 3 + (col // 3)][num]:  # 스도쿠의 3 x 3 박스에 대하여 사용된 적이 없는 숫자이면
                    candidates.append(num)                          # 후보군에 해당 숫자 추가
    return candidates

def DFS(depth):
    if depth == len(zeros):     # 모든 빈 칸이 채워졌으면
        return True             # return True

    row, col = zeros[depth]
    for num in getBlankCandidates(row, col):                # 현재 row, col 위치에 들어갈 수 있는 각각의 숫자에 대해
        board[row][col] = num                               # board[row][col]에 일단 값을 넣어보고
        dpRow[row][num] = True                              # 스도쿠의 row번째 행에 대하여 사용된 숫자 True
        dpCol[col][num] = True                              # 스도쿠의 col번째 열에 대하여 사용된 숫자 True
        dpSquare[(row // 3) * 3 + (col // 3)][num] = True   # 스도쿠의 3 x 3 박스에 대하여 사용된 숫자 True

        if DFS(depth + 1):          # 문제가 해결되었다면
            return True             # DFS 종료

        board[row][col] = 0                                 # board[row][col] 0으로 초기화
        dpRow[row][num] = False                             # 스도쿠의 row번째 행에 대하여 사용된 숫자 False
        dpCol[col][num] = False                             # 스도쿠의 col번째 열에 대하여 사용된 숫자 False
        dpSquare[(row // 3) * 3 + (col // 3)][num] = False  # 스도쿠의 3 x 3 박스에 대하여 사용된 숫자 False

    return False    # 모든 빈칸을 채울 수 없는 경우, return False

board = [list(map(int, list(input().rstrip()))) for _ in range(9)]
zeros = [(row, col) for row in range(9) for col in range(9) if not board[row][col]]
dpRow = [[False] * 10 for _ in range(9)]     # 9는 index, 10은 스도쿠의 1 - 9까지의 값을 의미
dpCol = [[False] * 10 for _ in range(9)]     # 9는 index, 10은 스도쿠의 1 - 9까지의 값을 의미
dpSquare = [[False] * 10 for _ in range(9)]  # 9는 index, 10은 스도쿠의 1 - 9까지의 값을 의미
for row in range(9):
    for col in range(9):
        num = board[row][col]       # 현재 row, col 위치의 값
        if num != 0:                # 빈 칸이 아니라면
            dpRow[row][num] = True  # 스도쿠의 row번째 행에 대하여 사용된 숫자 True
            dpCol[col][num] = True  # 스도쿠의 col번째 열에 대하여 사용된 숫자 True
            dpSquare[(row // 3) * 3 + (col // 3)][num] = True   # 스도쿠의 3 x 3 박스에 대하여 사용된 숫자 True
            
DFS(0)
for row in board:
    print(*row, sep='')