[BOJ] 2580 / 스도쿠 / Python 파이썬

[BOJ] 2580 / 스도쿠 / Python 파이썬

[BOJ]  2580 / 스도쿠 / Python 파이썬

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

2580번: 스도쿠

 

 

풀이

DFS 를 사용하는 백트래킹 문제이다.

 

여전히 습관적으로 모든 경로를 탐색하려고 시도하다 로컬에서도 time err 를 만나게 되었다.

고려해야 하는 경우만 탐색하도록 하자!

 

※Python 으로는 시간초과로 풀지 못하고, Pypy3 로 제출하여야 한다.

 

maps = []

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

zeroPosition = []
for y in range(9):
    for x in range(9):
        if not maps[y][x]:
            zeroPosition.append([y, x])

resFlag = False


def getNums(y, x):
    nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    for i in range(9):
        if maps[i][x] in nums:
            nums.remove(maps[i][x])
        if maps[y][i] in nums:
            nums.remove(maps[y][i])

    if not nums:
        return nums

    I = y//3
    J = x//3

    for i in range(I*3, I*3+3):
        for j in range(J*3, J*3+3):
            if not nums:
                return nums
            if maps[i][j] in nums:
                nums.remove(maps[i][j])
    return nums


def DFS(cnt):
    global resFlag
    if resFlag:
        return

    if cnt == len(zeroPosition):
        resFlag = True
        for y in range(9):
            print(" ".join(map(str, maps[y])))
        return

    Y, X = zeroPosition[cnt]

    numList = getNums(Y, X)

    for n in numList:
        maps[Y][X] = n
        DFS(cnt+1)
    maps[Y][X] = 0


DFS(0)