[백준] 2580 스도쿠 - 파이썬 (시간초과 풀이 및 해결)

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

2580번: 스도쿠

 

일반적인 백트래킹을 이용한 스도쿠문제이다. 1 ~ 9 사이의 숫자를 넣어보고 3x3, 가로, 세로 조건을 충족하면 다음 숫자를 넣고, 충족하지 않으면 이전의 조건으로 되돌리면 된다.

 

시간초과 풀이

import sys
input = sys.stdin.readline
sdoku = []

for _ in range(9):
    row = list(map(int, input().split()))
    sdoku.append(row)

zero_point = []

for i in range(9):
    for j in range(9):
        if sdoku[i][j] == 0:
            zero_point.append((i,j))
    

def check3x3(coords, val):
    x, y = 3*(coords[0]//3), 3*(coords[1]//3)
    for i in range(x, x+3):
        for j in range(y, y+3):
            if sdoku[i][j] == val:
                return False
    return True

def checkRow(coords, val):
    row = coords[0]
    for j in range(9):
        if sdoku[row][j] == val:
            return False
    
    col = coords[1]
    for i in range(9):
        if sdoku[i][col] == val:
            return False
    return True


def bt(index):
    if index == len(zero_point):
        for i in range(9):
            print(*sdoku[i])
        exit(0)

    for i in range(1, 10):
        x = zero_point[index][0]
        y = zero_point[index][1]
        
        
        if check3x3((x,y), i) and checkRow((x,y), i):
            sdoku[x][y] = i
            bt(index+1)
            sdoku[x][y] = 0

bt(0)

스도쿠 판에서 0인 점들만 탐색하는 코드인데, 0인 지점에 1 ~ 9 모든 숫자를 넣어 탐색하면 시간초과가 난다.

pypy3, python 둘 다 시간초과가 발생한다.

즉 0인 지점에 숫자를 넣기 전, 해당 지점에 넣을 수 없는 숫자들은 미리 제거하여 경우의 수를 줄여야 한다.

 

정답

def find_number(n,m):
    nums = [1,2,3,4,5,6,7,8,9]
    for i in range(9): # 가로 행 검사
        if sdoku[n][i] in nums:
            nums.remove(sdoku[n][i])
    
    for j in range(9): # 세로 열 검사
        if sdoku[j][m] in nums:
            nums.remove(sdoku[j][m])

    x_cor = (n // 3) * 3
    y_cor = (m // 3) * 3
    

    for i in range(x_cor, x_cor+3):
        for j in range(y_cor, y_cor+3):
            if sdoku[i][j] in nums:
                nums.remove(sdoku[i][j])
    # 행, 열, 3x3 까지 검사하여 0 자리에 가능한 숫자 list인 nums 반환
    return nums

def bt(index):
    global answer_flag
    if answer_flag == True:
        return
    
    if index == len(zero_point):
        for line in sdoku: # zero_point를 모두 체크한 경우 출력
            print(*line)
        answer_flag = True
        return

    i, j = zero_point[index] # 스도쿠에서 0인 좌표를 하나씩 가져온다
    able_nums = find_number(i,j)
    for num in able_nums:
        sdoku[i][j] = num
        bt(index + 1)
        sdoku[i][j] = 0

보기 쉽도록 입출력 코드는 제외하였다.

 

위에서 시간초과 나는 코드는 1 ~ 9의 모든 숫자를 넣어보고, 그 경우에 대해 조건을 검사하였지만

시간초과를 줄인 코드는 숫자를 넣어 조건을 검사하지 않고, 미리 해당 스도쿠판에서 불가능한 숫자는 제외하고 가능한 숫자들만 후보로 뽑는다. 후보인 숫자들은 따로 조건을 검사하지 않아도 되기 때문에 시간초과를 해결할 수 있다.

 

pypy3만 통과가 가능하다 ㅠ