파이썬으로 풀어보는 백준 2580번: 스도쿠

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

2580번: 스도쿠

 

내 풀이:

def row_check(y, x):
    check = [False] * 10
 
    for j in range(9):
        if not check[arr[y][j]]:
            if arr[y][j] != 0:
                check[arr[y][j]] = True
        else:
            return False
 
    return True
 
 
def col_check(y, x):
    check = [False] * 10
 
    for i in range(9):
        if not check[arr[i][x]]:
            if arr[i][x] != 0:
                check[arr[i][x]] = True
        else:
            return False
 
    return True
 
 
def square_check(y, x):
    ny = y // 3
    nx = x // 3
    check = [False] * 10
 
    for i in range(3*ny, 3*ny+3):
        for j in range(3*nx, 3*nx+3):
            if not check[arr[i][j]]:
                if arr[i][j] != 0:
                    check[arr[i][j]] = True
            else:
                return False
 
    return True
 
 
def fill(idx):
    global N, stop
    y, x = zero[idx]
    for num in range(1, 10):
        arr[y][x] = num
 
        if row_check(y, x) and col_check(y, x) and square_check(y, x):
            if idx == N-1:
                stop = True
                return
 
            fill(idx+1)
 
            if stop:
                return
 
        else:
            continue
    arr[y][x] = 0
 
 
arr = [list(map(int,input().split())) for _ in range(9)]
zero = []
for i in range(9):
    for j in range(9):
        if arr[i][j] == 0:
            zero.append((i, j))
 
N = len(zero)
stop = False
fill(0)
 
for i in range(9):
    print(*arr[i])

PyPy3, 81% 시간 초과

Python3, 11% 시간 초과

빈 공간인 좌표를 모두 저장한 후 각 좌표에 대해서 1부터 9까지 넣어봄과 동시에 가로, 세로, 사각형을 검토한다. 백트레킹에만 중점을 두고 있는 그대로 구현할 시 시간 초과가 나는 것을 확인할 수 있다.

 

 

import sys
 
def row_check(y, x):
    check = [False] * 10
 
    for j in range(9):
        if not check[arr[y][j]]:
            if arr[y][j] != 0:
                check[arr[y][j]] = True
        else:
            return False
    return True
 
 
def col_check(y, x):
    check = [False] * 10
 
    for i in range(9):
        if not check[arr[i][x]]:
            if arr[i][x] != 0:
                check[arr[i][x]] = True
        else:
            return False
    return True
 
 
def square_check(y, x):
    ny = y // 3
    nx = x // 3
    check = [False] * 10
 
    for i in range(3*ny, 3*ny+3):
        for j in range(3*nx, 3*nx+3):
            if not check[arr[i][j]]:
                if arr[i][j] != 0:
                    check[arr[i][j]] = True
            else:
                return False
    return True
 
 
def fill(idx):
    global N
    if idx == N:
        for i in range(9):
            print(*arr[i])
        sys.exit()
 
    y, x = zero[idx]
    can_fill = [False] + [True] * 9
 
    for k in range(9):
        can_fill[arr[y][k]] = False
        can_fill[arr[k][x]] = False
 
    ny = y // 3 * 3
    nx = x // 3 * 3
 
    for i in range(ny, ny+3):
        for j in range(nx, nx+3):
            can_fill[arr[i][j]] = False
    can_fill = [idx+1 for idx, i in enumerate(can_fill[1:]) if i]
 
    for num in can_fill:
        arr[y][x] = num
        fill(idx+1)
        arr[y][x] = 0
 
 
arr = [list(map(int,input().split())) for _ in range(9)]
zero = []
 
for i in range(9):
    for j in range(9):
        if arr[i][j] == 0:
            zero.append((i, j))
 
N = len(zero)
fill(0)

PyPy3, 1112ms

Python3, 81% 시간 초과

숫자를 넣어보고 체크하는 방식에서 아예 넣을 수 있는 숫자를 먼저 확인한 후 가능한 수만 넣는 방식으로 수정하였다. PyPy3로는 통과하였으나 Python3로는 수정 전 PyPy3가 걸렸던 샘플인 81%를 넘지 못하고 시간 초과가 났다.