이젠 스도쿠 천재 (골드4)

#2580 스도쿠 https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

틀린코드 (with while and que)

matrix = []
target = []
# get input and save target position
for i in range(9):
    tmp = input().split()
    l = []
    for j in range(9):
        if int(tmp[j]) == 0:
            target.append([i, j])
        l.append(int(tmp[j]))
    matrix.append(l)


def check(x, y):
    nums = [True]*10

    # check row
    for n in matrix[x]:
        nums[n] = False
    # check column
    for i in range(9):
        nums[matrix[i][y]] = False
    # check box
    for i in range((x//3)*3, (x//3)*3+3):
        for j in range((y//3)*3, (y//3)*3+3):
            nums[matrix[i][j]] = False

    result = [x for x in range(1, 10) if nums[x]]
    return result


while target:
    t = target.pop(0)
    x, y = t
    result = check(x, y)
    if len(result) == 1:
        matrix[x][y] = result[0]
    else:
        target.append(t)

for i in matrix:
    print(" ".join(map(str, i)))

열심히 짰다.

1. 입력을 받으면서 빈칸을 별도로 저장한다.

2. 스도쿠의 조건에 맞춰서 각 빈칸에 적절한 수를 찾아내는 함수를 만든다.

3. 모든 칸을 돌아가면서 진행한다.

 

테스트 케이스는 맞췄지만 시간초과로 틀렸다.

 

while문을 사용해서 답이 나오는 경우는 바로 작성하고, 아닌 경우는 큐의 후순위로 돌리면서 진행했다.

당연히 오래걸리지.

 

이걸 재귀적으로 변경해 해결했다.

 

정답코드 (with DFS)

matrix = []
target = []
# get input and save target position
for i in range(9):
    tmp = input().split()
    l = []
    for j in range(9):
        if int(tmp[j]) == 0:
            target.append([i, j])
        l.append(int(tmp[j]))
    matrix.append(l)

for i in matrix:
    print(i)


def check(x, y):
    nums = [True]*10

    # check row
    for n in matrix[x]:
        nums[n] = False
    # check column
    for i in range(9):
        nums[matrix[i][y]] = False
    # check box
    for i in range((x//3)*3, (x//3)*3+3):
        for j in range((y//3)*3, (y//3)*3+3):
            nums[matrix[i][j]] = False

    return nums


def solve(idx):
    if idx == len(target):
        for i in matrix:
            print(*i)
        exit()
    x, y = target[idx]
    result = check(x, y)
    for i in range(1, 9):
        if result[i]:
            matrix[x][y] = i
            solve(idx+1)
            matrix[x][y] = 0


solve(0)

while로 짰던 코드는 빈칸에 들어갈 수 있는 수가 여러개인 경우 후순위로 보내면서 진행했다. 즉 영원히 끝나지 않을 수 있는 코드이다.

-> 시간초과

 

그래서 DFS 재귀를 활용해 빈칸에 들어갈 수 있는 수가 여러개인 경우 재귀적으로 처리했다. (모든 경우의 수를 살펴봤다고 할 수 있다.)

 

pypy로 제출해 아슬아슬하게 통과했다.

 

+) 팁

 

* : asterisk. 보통은 곱셈 연산자로 알고있지만 이는 활용이 다양하다.

 

*args : args가 가지고 있는 모든 원소를 반환한다.

 

즉 

l = [1,2,3,4]
print(*l)

이렇게 작성할 경우 l의 원소들을 출력한다 -> 1 2 3 4

 

아래 블로그에 잘 정리되어 있다. (내꺼 아님)

https://mingrammer.com/understanding-the-asterisk-of-python/

파이썬의 Asterisk(*) 이해하기