[PyPy] [DFS] 백준 2580 스도쿠

문제

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

코드

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

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

def rowcheck(r,a):
    for i in range(9):
        if a==graph[r][i]:
            return False
    return True
def colcheck(c,a):
    for i in range(9):
        if a==graph[i][c]:
            return False
    return True
def rectcheck(r,c,a):
    nx=r//3 * 3
    ny=c//3 * 3
    for i in range(3):
        for j in range(3):
            if a==graph[nx+i][ny+j]:
                return False
    return True
def dfs(x):
    if x==len(blank):
        for i in range(9):
            print(*graph[i])
        exit(0)
     
    for i in range(10):
        r=blank[x][0]
        c=blank[x][1]
        if rowcheck(r,i) and colcheck(c,i) and rectcheck(r,c,i):
            graph[r][c]=i
            dfs(x+1)
            graph[r][c]=0
dfs(0)

생각 정리

백트래킹을 활용한 문제였다.