[BOJ] 스도쿠

---

코드

import sys
input = sys.stdin.readline

board = [list(map(int, list(input().rstrip()))) for _ in range(9)]    # INPUT
blanks = [(i, j) for i in range(9) for j in range(9) if board[i][j] == 0]

def candidate(i, j):
    ret = set([i+1 for i in range(9)])
    
    # 같은 행/열, 소속된 3x3 블록에서 사용된 수
    used = set(board[i] + [board[r][j] for r in range(9)] + [board[r][c] for r in range(3*(i//3),3*(i//3)+3) for c in range(3*(j//3), 3*(j//3) +3)])

    return ret - used    # 1~9중 사용된 수 제외

def dfs(count):
    # 이 if문에 걸리면 스도쿠가 해결됐다는 것이다
    if count == len(blanks):
        for row in board:
            print(''.join(map(str, row)))
        sys.exit()

    i, j = blanks[count]
    candidates = candidate(i, j)
    for c in candidates:    # 넣을 숫자가 없으면 이대로 함수는 종료됨
        board[i][j] = c
        dfs(count+1)
        board[i][j] = 0    # 정답이 아닐 수 있으니 다시 비워줘야함

dfs(0)

결과

풀이 방법

• 백트래킹을 활용하는 문제이다. 시간초과에 상당히 까다롭다.
• 빈 좌표에 들어갈 수 있는 숫자들은 해당 좌표의 같은 행/열, 그리고 좌표가 소속된 3x3 블록에서 사용하지 않은 숫자여야 한다.
• DFS로 빈 좌표에 숫자를 넣어보다가 이후의 빈 좌표에 넣을 숫자가 없어 정답이 아니라고 판단되면 다시 비우고 다른 숫자를 넣어본다.
• DFS의 깊이가 빈 좌표의 개수와 같아지면, 스도쿠의 모든 빈 좌표가 DFS수행도중 종료되지 않고 정상적으로 채워진 것이므로 완성된 결과를 출력한다.
• 백트래킹에서 나는 자꾸 dfs 재귀수행 후에 상태를 원상태로 복구하는 이유를 잊을 때가 있다. 원상태로 복구하는 건 다음 dfs 수행을 위한 작업이고 이미 수행중인 dfs에서는 이전 상태 그대로 유지되고 아무런 영향을 받지 않는다.

---