[Back Tracking] 백준 2580번 : 스도쿠 파이썬

 

생각하기

0인 칸에 대해서 이 칸에 스도쿠 룰에 맞는 숫자를 넣고 다음 0인 칸에 대해서 룰에 맞는 숫자를 넣는 식으로 생각을 했다.

조건이 안맞으면 바로 이전으로 가서 다시 한번 숫자를 넣어보는 식으로 생각을 했다

 

prunning 조건 검사

• 해당 0이 있는 row에 지금 들어갈 같은 수를 가진 아이가 있는지 검사
• 해당 0이 있는 col에 지금 들어갈 같은 수를 가진 아이가 있는지 검사
• 0이 속한 아홉개의 섹션 안에 지금 들어갈 같은 수를 가진 아이가 있는지 검사

위의 세가지 조건을 0자리에 들어갈 1 ~ 9까지에 대해서 검사를 하고 맞으면 recursive하게 다음으로, 틀리면 backtracking을 진행한다

 

9*9를 검사하지 않고 0인 것들만 보기

입력을 받을 때, 0인 칸의 row idx와 col idx를 미리 blank 라는 리스트 안에 튜플로 저장해 놓고 이들을 대상으로만 recursive한 함수를 돌리면 어떠할까 생각했다.

 

구현하기

prunning을 위해 해당 메모이제이션 배열을 선언했다

• row_memo : 각 행에서 1~9의 숫자가 있는지 체크
• col_memo : 각 열에서 1~9의 숫자가 있는지 체크
• box : 각 섹션(9개)에서 1~9의 숫자가 있는지 체크

data를 입력받을 때, 9*9 배열을 검사하여 위의 3개의 메모이제이션 항목들을 업데이트 해준다

 

• blank : 0인 위치가 튜플로 들어있는 리스트

data를 입력받을 때, 9*9 배열을 검사하여 0인 위치를 (row, col)로 튜플로 append해준다.

• box_loc 메소드 : 9개의 섹션중에서 어느 섹션에 해당하는지 알려주는 메소드
• sudoku : recursive한 방법을 통해 1~9까지를 검사하며 data 배열에 넣는다

backtracking의 중요 원칙인 준비 -> 호출 -> 원래대로 돌려놓기  를 철저히 지켜가며 sudoku 메소드는 재귀를 진행한다

 

import sys
input = sys.stdin.readline


data = []

blank = []

row_memo = [[False]*10 for _ in range(9)]
col_memo = [[False]*10 for _ in range(9)]
box = [[False]*10 for _ in range(9)]

# print(row_memo)
# print(col_memo)

def box_loc(i, j):
    if i//3 == 0:
        return j//3
    
    elif i//3 == 1:
        return 3 + (j//3)

    else:
        return 6 + (j//3)

for i in range(0, 9):
    data.append(list(map(int,  input().split())))
    for j in range(0, 9):
        if data[i][j] == 0:
            blank.append((i, j))
        else:
            box[box_loc(i, j)][data[i][j]] = True
            row_memo[i][data[i][j]] = True
            col_memo[j][data[i][j]] = True

# print("------data----------")
# print(data)
# print("------blank--------")
# print(blank)
# print("------box--------")
# print(box)

# print(blank[1][1])

            

def sudoku(blank_idx):

    if blank_idx == len(blank):
        for i in range(9):
            for j in range(9):
                print(data[i][j], end=' ')
            print()
        sys.exit()

    row = blank[blank_idx][0]
    col = blank[blank_idx][1]

    for n in range(1, 10):
        if row_memo[row][n] == False and col_memo[col][n] == False and box[box_loc(row,col)][n] == False:
            data[row][col] = n
            row_memo[row][n] = True
            col_memo[col][n] = True
            box[box_loc(row,col)][n] = True
            sudoku(blank_idx+1)
            row_memo[row][n] = False
            col_memo[col][n] = False
            box[box_loc(row,col)][n] = False

sudoku(0)

결과

python3 에서는 시간초과가 발생했고 pypy3에서는 820으로 넉넉히 통과했다

 

 

box의 섹션을 판단하는 식중에서 나처럼 조건문 쓰지 않고

식으로 쓴다면 (row//3)*3 + col//3이 되겠다

이 식을 적용해서 box_loc 메소드를 바꾼다면

시간이 더 줄어든 것을 볼 수 있다

 

 

 

하지만 늘 백트레킹 문제에서 해결되지 않는 의문점..

python3 에서는 왜 시간초과가 뜰까...?