[Python] 백준 / gold / 2580 : 스도쿠

문제 링크 : https://www.acmicpc.net/problem/2580

알고리즘 분류 - 백트래킹

백트래킹 문제 로직을 짜는데 약하다고 생각이 들었었다. 이 문제를 풀면서 조금 자신감을 찾은것 같다. 백트래킹 문제를 풀때는 상태 트리를 만들면 좋다. 내 생각을 정리해줄 수 있게 된다.

스도쿠 문제를 어떻게 백트래킹으로 풀 수 있을까 고민했는데, 빈칸의 좌표들을 먼저 blank 리스트에 담았다. 빈칸 들을 A, B, C, D 라고 했을 때, 먼저 A 부터 고려하면 A에 들어갈 수 있는 수의 후보들이 있을 것이다. 그 수들을 1, 3, 5 라고 했을 때, A=1 일 경우를 가지고 B 케이스를 탐색하기 시작하는 거다. 쭉 같은 방식으로 진행하다가 모순이 생기면 뒤로 돌아온다. A=1 일 경우 탐색을하다가 모순을 발견하면 다시 돌아와서 A=3 일 경우를 가지고 다시 탐색을 시작한다.

2 가지를 얻어간다.

1. 아무것도 return 하지 않으면 ( return None 이면 ) if not dfs() 에 걸린다.
2. 백트래킹 문제를 풀때 상태 공간 트리를 그리자.

파이썬 코드

import sys
graph = []
blank = []
for i in range(9):
    graph.append(list(map(int, sys.stdin.readline().split())))
    for j in range(9):
        if graph[i][j] == 0:
            blank.append((i, j))


def dfs(idx):
    if idx == len(blank):
        return True
    x, y = blank[idx]

    flag = False
    for n in range(1, 10):
        if checkRow(x, y, n) and checkCol(x, y, n) and checkBox(x, y, n):
            flag = True
            graph[x][y] = n
            if not dfs(idx+1):
                graph[x][y] = 0
                flag = False

    return True if flag else False


def checkRow(x, y, n):
    for i in range(9):
        if i != y and graph[x][i] == n:
            return False
    return True


def checkCol(x, y, n):
    for i in range(9):
        if x != i and graph[i][y] == n:
            return False
    return True


def checkBox(x, y, n):
    a = 3 * (x//3)
    b = 3 * (y//3)
    for i in range(a, a + 3):
        for j in range(b, b + 3):
            if (i, j) != (x, y) and graph[i][j] == n:
                return False
    return True


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