[BOJ] 백준 2239번 문제 풀이 (Python)

1. 문제 풀이

backtracking을 사용하여 스도쿠 퍼즐에서 비어있는 칸에 해당되는 경우의 수를 모두 탐색하는 방법으로 문제를 풀었다.

오늘 문제와 유사한 문제로 2580번 스도쿠가 있다. 해당 문제에 대한 풀이를 이 곳에서 확인할 수 있다.

2. 코드

import sys
def input(): return sys.stdin.readline().rstrip()

def dfs(idx):
    if idx == len(empty):
        for i in range(9):
            print("".join(map(str,matrix[i])))
        return True
    i, j = empty[idx][0], empty[idx][1]
    total_number = set([num for num in range(1,10)])
    used = set(matrix[i] + [matrix[r][j] for r in range(9)] + [matrix[r][c] for r in range(3*(i//3),3*(i//3)+3) for c in range(3*(j//3), 3*(j//3) +3)])
    for num in sorted(total_number - used):
        matrix[i][j] = num
        if dfs(idx+1):
            return True
        matrix[i][j] = 0
    return False

matrix = [list(map(int,list(input()))) for _ in range(9)]
empty = [(i,j) for i in range(9) for j in range(9) if not matrix[i][j]]
dfs(0)