[baekjoon] 2580 스도쿠 (python)

문제

---

9 x 9 2차원 배열이 주어지면 스도쿠 규칙에 의거해서 빈칸에 숫자를 채우면 된다.

접근법

---

가로, 세로, 9칸 구역에 같은 숫자가 없는지 판단하고, 넣을 수 있는 숫자를 넣고 다음 빈칸으로 넘어간다.
다음 빈칸에서 불가능하면 원래 빈칸으로 넘어와서 다른 숫자를 넣어본다 (백트래킹)

pypy로 하면 통과하는데 python3로 제출하면 계속 시간초과가 난다.
처음엔 빈칸들을 deque로 관리해서 그냥 배열로 변경해보고,
1~9 숫자를 넣을 때마다 중복체크 해주던 로직을 따로 빼서, 가능한 숫자들만 가지고 트래킹을 해봐도 시간초과다.
나머지는 필요한 로직 같은데.. cpp로 하면 되려나
시간초과를 잡는 것 보다 다른 공부를 하는게 생산적일 것 같아 일단은 넘어간다.

Code

---

# input
board = [list(map(int, input().split())) for _ in range(9)]

blank = [(i, j) for i in range(9) for j in range(9) if board[i][j] == 0]

def check_blank(idx):
    if idx == len(blank):
        # print
        for i in range(9):
            print(' '.join(map(str,board[i])))
        exit()

    i, j = blank[idx]

    pi = (i // 3) * 3
    pj = (j // 3) * 3
    num_list = []
    for num in range(1, 10):
        pos = True
        for k in range(9): # 가로, 세로, 정사각형 구역에 하나라도 중복되면 불가능
            if board[i][k] == num or board[k][j] == num or board[pi + k // 3][pj + k % 3] == num:
                pos = False
                break
        if pos:
            num_list.append(num)

    for num in num_list:
        board[i][j] = num
        check_blank(idx + 1)
        board[i][j] = 0


check_blank(0)

건전한 피드백은 언제나 환영입니다 :D