[백준] 2580 파이썬(python) : 스토쿠 - (★)

2580번 : 스토쿠

 

 

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

def checkRow(x, a): #2
    for i in range(9):
        if a == graph[x][i]:
            return False
    return True

def checkCol(y, a): #3
    for i in range(9):
        if a == graph[i][y]:
            return False
    return True

def checkRect(x, y, a): #4
    nx = (x//3)*3
    ny = (y//3)*3
    for i in range(3):
        for j in range(3):
            if a == graph[nx+i][ny+j]: #5
                return False
    return True

def backTracking(idx):
    if idx == len(blank): #6
        for i in range(9):
            print(*graph[i])
        exit(0)
    for i in range(1, 10): #7
        x = blank[idx][0]
        y = blank[idx][1]
        if checkRow(x, i) and checkCol(y, i) and checkRect(x, y, i):
            graph[x][y] = i
            backTracking(idx+1) #8
            graph[x][y] = 0
backTracking(0)

 

#1 : 그래프에서 0인 위치 blank에 삽입

#2 : x축에 대하여 같은 숫자가 있으면 False 없으면 True 리턴

#3 : y축에 대하여 같은 숫자가 있으면 False 없으면 True 리턴

#4, 5 : 현 위치가 포함된 작은 사각형안에서 같은 숫자가 있으면 False 없으면 True 리턴

#6 : 백트래킹을 수행하면서 빈칸(0)을 모두 채우면 graph 한줄씩 출력

#7 : 숫자 1~9까지 빈칸에 삽입하기 위해 반복

#8 : x축, y축, 작은 사각형 안에 모두 같은 숫자가 없어 True를 리턴하면 graph[i][j] = i로 빈칸에 숫자를 채워주고 다음 빈칸을 찾기위해 idx+1해서 백트래킹