백준 - 스도쿠(2580)

문제 링크 ▶︎ 백준 스도쿠 2580

문제 전략

이 문제는 백트래킹 문제이다.
스도쿠의 전략에 맞게 ① 해당 행, ② 해당 열, ③ 해당 3X3 정사각형 을 검사하는 함수가 있어야 한다.

빈칸은 0으로 채워두고, DFS 로 빈칸(0) 을 탐색 시작한다.
빈칸을 찾으면 1 ~ 9의 숫자 중 스도쿠 3가지 전략에 맞는 수를 넣고 재귀함수를 호출한 뒤 다시 빈칸(0)으로 바꿔 놓는다.
(틀린 노드는 회수 - 백트래킹)

만약 모든 빈칸이 채워진다면 그게 답이므로 바로 탈출하고 출력한다.

코드

def row(y,n): # y행 체크
    for i in range(9):
        if graph[y][i] == n:
            return False
    return True

def col(x,n): # x열 체크
    for j in range(9):
        if graph[j][x] == n:
            return False
    return True

def square(y,x,n): # 3x3 체크
    for i in range(3):
        for j in range(3):
            if graph[y//3*3+i][x//3*3+j] == n:
                return False
    return True

def dfs(n):
    if n == len(blank): # 찾으면 탈출
        for k in graph:
            print(*k)
        exit(0)
        
    x = blank[n][1]
    y = blank[n][0]

    for i in range(1,10):
        if row(y,i) and col(x,i) and square(y,x,i):
            graph[y][x] = i
            dfs(n+1)
            graph[y][x] = 0

import sys
input = sys.stdin.readline

blank = []
graph = [list(map(int,input().split())) for _ in range(9)]

for i in range(9):
    for j in range(9):
        if graph[i][j] == 0:
            blank.append([i,j])

dfs(0)

개선 사항

시간 복잡도를 더 줄이는 방법을 고민.