백준 2580_스도쿠 [python/파이썬]

# pypy3로 제출해야 시간초과가 나지 않습니다.
sudoku = []
for _ in range(9):
    sudoku.append(list(map(int, input().split())))
 
 
def print_sudoku(sudoku):
    for line in sudoku:
        print(*line)
    print()
 
def check_sudoku(i,j, candidate):
    global sudoku
    # 세로 체크
    for x in range(9):
        if sudoku[x][j] == candidate:
            return False
    # 가로 체크
    for y in range(9):
        if sudoku[i][y] == candidate:
            return False
    # 3x3 체크
    for x in range((i//3)*3, (i//3)*3+3):
        for y in range((j//3)*3, (j//3)*3+3):
            if sudoku[x][y] == candidate:
                return False
 
    return True
 
flag = 0
 
def make_sudoku():
    global flag, sudoku
    for x in range(9):
        for y in range(9):
            if sudoku[x][y] == 0:
                for i in range(1,10):
                    if check_sudoku(x,y,i): # 비어있는 곳에 넣을 숫자 체크
                        sudoku[x][y] = i
                        make_sudoku() # 비어있는 곳에 숫자를 집어넣고 다음 비어있는 곳 탐색 진행
                        if flag == 1: # 모두 정상적으로 채워졌으므로 return
                            return
                        sudoku[x][y] = 0 # 다시 원래대로 복구
                return # 1~9까지 어떤 숫자도 맞지 않으므로 이전으로 되돌아간다.
    flag = 1 # 모두 정상적으로 채워졌음을 표시
    return
 
 
make_sudoku()
print_sudoku(sudoku)

 

 

백트래킹과 재귀에 익숙하지 않아 많은 시간을 쏟은 문제였다.

그나마다도 python으로 제출할 시 시간초과가 떠서 pypy3로 제출했다. 어렵지만 성장하기 좋은 문제..