[백준/python]2580번 스도쿠 - backtracking

스도쿠 문제다. 스도쿠 문제를 풀어봤다면 백트래킹으로 풀어야 된다는 생각이 자연스럽게 떠오를 것 같다.

#스도쿠
sdoku = []
start = []
for i in range(9):
    line = list(map(int, input().split()))
    for j in range(9):
        if line[j]==0 :
            start.append([i,j])
    
    sdoku.append( line )

def DFS(idx):
    global ans
    if idx == len(start) :
        for i in range(9):
            print(' '.join(map(str, sdoku[i])))
        return 1
        
    x,y=start[idx]
    check_r,check_c,check_s = [0 for _ in range(10)],[0 for _ in range(10)],[0 for _ in range(10)]    
    
    section_x = (x//3) *3
    section_y = (y//3) *3
    
    #있는 거 부터 체크
    for i in range(9):
        row = sdoku[x][i]
        if row !=0:
            check_r[row] = 1
            
    for i in range(9):
        col = sdoku[i][y]
        if col !=0:
            check_c[col]=1
    
    for i in range(3):
        for j in range(3):
            sqr = sdoku[section_x+i][section_y+j]
            if sqr !=0 :
                check_s[sqr]=1
       
    
    
    for i in range(1,10):
      
        if check_r[i] ==0 and check_c[i]==0 and check_s[i]==0:
            sdoku[x][y]=i
            if DFS(idx+1) ==1:
                return 1
            sdoku[x][y]=0
    
        if i == 9:
            return 0
    
    return 0

DFS(0)

구현

1. 입력값을 받으면서 동시에 채워지지 않은 값을 start 배열에 저장한다.
2. start 배열에 있는 모든 빈 칸을 채우면 DFS를 종료하고 완성된 스도쿠를 출력한다. 출력 이후 모든 재귀를 종료하기 위해 DFS 함수의 결과값으로 1을 리턴한다. DFS 내부에서 재귀를 실행하는 코드에서 return 값이 1이면 다시 한 번 1을 리턴하는 방식으로 모든 재귀가 종료된다.
3. 스도쿠에서 9개의 사각형 구역의 왼쪽 모서리를 section_x, section_y로 저장한다.
4. 빈 칸과 동일한 행과 열, 동일한 사각형에 어떤 숫자가 있는 지 표시한다.
5. 4번에서 체크한 숫자를 제외한 숫자를 이용하여 방문 표시를 하고 백트래킹을 이용하여 빈 칸을 채워나간다.