[백준 2580, Gold IV] 스도쿠

📒문제

🎈풀이

import sys

def chkRow(row, N): # 같은 열에 N과 똑같은 숫자가 있는지 확인하기
    for i in range(9):
        if arr[row][i] == N:
            return False

    return True

def chkCol(col, N): # 같은 행에 N과 똑같은 숫자가 있는지 확인하기
    for i in range(9):
        if arr[i][col] == N:
            return False

    return True

def chkRect(row, col, N): # 3*3 사각형에 N과 똑같은 숫자가 있는지 확인하기
    sRow = row//3 * 3
    sCol = col//3 * 3 
    # blank값이 속하는 사각형을 특정하는 곳, 이걸 어떻게 해야 될지 애매했었는데 간단한 수학적 아이디어로 해결이 가능했다. 잘 숙지해두기
	
    # 사각형 내에서 같은 숫자가 존재하는지를 판단
    for i in range(sRow, sRow+3):
        for j in range(sCol, sCol+3):
            if arr[i][j] == N:
                return False
    

    return True


def dfs(idx): 
	# idx = blank값들의 idx / 백트래킹에선 이 depth의 기준을 무엇으로 잡느냐가 제일 중요하다
    
    if idx == len(blank): # 모든 blank에 값을 올바르게 넣었다면 출력후 종료 (재귀 종료조건)
        for i in range(9):
            for j in range(9):
                print(arr[i][j], end = " ")
            print()

        exit(0)
    
    for i in range(1, 10): # blank 위치에 들어갈 값 선정 (1부터 9까지 다 넣어본다.)
        row = blank[idx][0]
        col = blank[idx][1]

        if chkRow(row, i) and chkCol(col, i) and chkRect(row, col, i):
            arr[row][col] = i # 만일 해당 blank에 i를 넣는 것이 조건에 맞다면, 값을 넣는다.
            dfs(idx+1) # 이제 다음 blank를 해결하러 ㄱㄱ
            arr[row][col] = 0 # 만일 조건에 맞지 않다면 이걸 0으로 되돌리기
            
            # 이렇게 조건에 맞지 않는 것을 되돌리는 형식은 (값 바꾸고 -> 재귀 돌린 뒤 -> 값 원상복구) 솔직히 잘 이해가 되진 않는데, 그냥 이런 형식이라고 생각해주면 될 것 같다. 따로 원상복구를 위한 tmp를 만들지 않아도 이렇게 풀면 해결된다. 잘 알아두자.
		

arr = []
for _ in range(9):
    arr.append(list(map(int, sys.stdin.readline().split())))

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

그래도 나름 N과 M 문제도 풀고 N-Queen문제도 어렵지 않게 이해했어서 이 문제도 쉽게 풀 수 있을 것이라고 생각했는데 그렇지는 않았다...ㅠㅠ 역시 백트래킹은 어렵다.

자세한 설명은 주석에 달아두었다. 오늘 저녁에 N-Queen문제와 이 문제는 꼭 다시 풀어보자.