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

1. 풀이

스도쿠를 푸는 문제이다. 처음에 풀이를 생각했을 때는 단순히 스도쿠에서 빈 칸을 찾아 숫자를 채워넣는 것이라고 생각했다. 따라서 빈 칸에 들어갈 숫자가 한 번에 결정될 수 있는 것부터 차례대로 해결하면 된다고 생각했다. 하지만 다음과 같은 테스트 케이스에서 막혔다.

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

빈 칸에 들어갈 숫자가 한 번에 결정될 수 있는 것이 아무 것도 없기 때문에 무한 루프에 빠지게 되었고 풀이 방식을 바꾸어야 했다.

그 결과 다음과 같은 방식을 사용해 문제를 풀었다.

• DFS: 트리의 각 노드를 스도쿠의 빈 칸으로 설정하고 모든 노드를 방문할 수 있으면 종료한다. 다음 노드를 방문하려면 현재 노드에 사용할 수 있는 숫자가 있어야한다. 즉, 현재 노드가 가리키는 빈 칸에 들어갈 수 있는 숫자가 없는 경우를 가리킨다.
• Backtracking: 다음 노드를 방문할 수 없는 경우 해당 지점에서 탐색을 멈춘 후 아직 경우의 수가 남은 노드로 거슬러 올라간 다음 탐색을 진행한다. DFS를 이용하기 때문에 경우의 수가 남은 노드는 부모 노드이므로 ‘거슬러 올라간다’는 표현을 사용하였다. 이 때 ‘거슬러 올라가는 것’을 Backtracking이라 한다.

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

def dfs(idx):
    if idx >= len(node):
        return True   
    i,j = node[idx]
    r,c = (i //3) * 3, (j //3) * 3
    nums1 = set([1,2,3,4,5,6,7,8,9])
    nums2 = set(sudoku[i] + [sudoku[k][j] for k in range(9)] +sudoku[r][c:c+3] + sudoku[r+1][c:c+3] + sudoku[r+2][c:c+3])
    for num in nums1 - nums2:
        sudoku[i][j] = num
        if dfs(idx+1): return True
        sudoku[i][j] = 0
    return False
        
sudoku = [list(map(int,input().split())) for _ in range(9)]
node = [(i,j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]

dfs(0)

for i in range(9):
    for j in range(9):
        print(sudoku[i][j],end=' ')
    print()

Backtracking을 조금 더 자세히 설명하면 해를 탐색하는 도중 지금의 경로가 더이상 해에 도달할 수 없을 것 같으면 그 경로를 더이상 탐색하지 않고 경로를 되돌아가 새로운 경로를 탐색하는 방법이다. 해에 도달할 수 있는 유망한(promising) 경로만을 탐색한다고 볼 수 있다. Backtracking은 해에 도달할 수 없는 경우 그 경로를 잘라내고(prunning) 더이상 진행하지 않기 때문에 모든 경우의 수를 탐색하는 DFS보다 더 빠르다고 할 수 있다.

이와 비슷한 문제로는 N-Queens 문제가 있다. Backtracking을 공부하는데 아주 기초가 되는 문제이기 때문에 Backtracking을 처음 접한다면 N-Queens 문제를 먼저 풀고 오는 것을 추천한다.