[백준/Python] 스도쿠

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

2580번: 스도쿠

import sys

sudoku = [list(map(int, sys.stdin.readline().split())) for _ in range(9)] # 스도쿠 숫자 리스트
zeros = [(i, j) for i in range(9) for j in range(9) if sudoku[i][j] == 0] # 해결해야 할 칸 리스트
flag = False # 답이 출력되었는지 확인하는 변수

# 가능한 숫자 검사 메서드
def get_possible(i, j):
	possible = [1, 2, 3, 4, 5, 6, 7, 8, 9]

        # 행열 검사
	for k in range(9):
		if sudoku[i][k] in possible:
			possible.remove(sudoku[i][k])
		if sudoku[k][j] in possible:
			possible.remove(sudoku[k][j])

        # 3*3 박스 검사
	for a in range(i//3*3, i//3*3+3):
		for b in range(j//3*3, j//3*3+3):
			if sudoku[a][b] in possible:
				possible.remove(sudoku[a][b])

	return possible

def dfs(n):
	global flag
	
	if flag: # 답이 이미 출력된 경우
		return
		
	if n == len(zeros): # 더 이상 탐색할 숫자가 없는 경우 답을 출력
		for row in sudoku:
			print(*row)
		flag = True
		return
	else:
		i, j = zeros[n] # 해결해야 할 칸
		possible = get_possible(i, j) # 해결해야 할 칸의 가능한 숫자 리스트

		for num in possible:
			sudoku[i][j] = num # 가능한 숫자 하나를 넣어줌
			dfs(n + 1) # 다음 해결해야 할 칸으로 넘어감
			sudoku[i][j] = 0 # 위의 가능한 숫자가 아닐 경우를 대비한 초기화

dfs(0)

1. 필요한 정보를 입력받고 sudoku 에서 0만 뽑아 해결해야 할 칸 리스트를 뽑는다.

2. DFS를 수행한다.

    2-1. 해결해야 할 칸(i, j)의 가능한 숫자 리스트를 가져온다. get_possible 메서드는 행열과 3*3 박스를 검사하여 가능한 숫자 리스트를  뽑는다.

    2-2. 가능한 숫자를 하나 넣어주고 다음 해결해야 할 칸으로 넘어간다.

    2-3. 더 이상 해결해야 할 숫자가 없는 경우 답을 출력한다.

    2-4. 답이 이미 출력된 경우 return