글 읽기 - 고수님들 차이점을 모르겠는데 부탁드립니다.

jin03114 3년 전 0

처음에 코드를 이렇게 써서 시간초과가 났었는데

52줄

x, y = zeros[cnt]

for j in range(1,10,1):

flag = Check(x,y,j)

if flag:

이런식으로 바꾸니까 시간초과 없이 잘되는데, 왜 되는지를 잘 모르겠습니다.

원래쓴 코드에서도 (cnt ~ n) 까지니까 x,y = zeros[cnt] 이런식으로 굳이 안써도 답을 구하는데는 어차피 똑같은 수의 재귀함수가 돌아갈거 같은데 어떨때 다른지 알려주시면 감사하겠습니다...

import sys
limit_number = 300000
sys.setrecursionlimit(limit_number)

graph = [ list(map(int,input().split())) for _ in range(9) ]

zeros = []

# 숫자 검사를 위해 필요한 dictionary
rows = [
    dict() for _ in range(9)
]
cols = [
    dict() for _ in range(9)
]
square = [
    dict() for _ in range(9)
]

# 스도쿠에서 0 인 곳을 zeros 리스트에 추가
for i in range(9):
    for j in range(9):
        num = graph[i][j]
        if num == 0:
            zeros.append((i,j))
        else:
            rows[i][num] = True
            cols[j][num] = True
            # Main Point
            q = i//3 * 3 + j//3
            square[q][num] = True

n = len(zeros)

def Check(x, y, num):
    if num in rows[x]:
        return 0
    if num in cols[y]:
        return 0
    if num in square[x//3 * 3 + y // 3]:
        return 0
    return 1

def DFS(cnt):
    if cnt==n:
        for i in range(9):
            for j in range(9):
                print(graph[i][j], end=' ')
            print()
        exit()

    for i in range(cnt, n, 1):
        x, y = zeros[i]
        for j in range(1,10,1):
            flag = Check(x,y,j)
            if flag:
                graph[x][y] = j
                rows[x][j] = True
                cols[y][j] = True
                square[x//3 * 3 + y // 3][j] = True

                DFS(cnt+1)
                del rows[x][j]
                del cols[y][j]
                del square[x//3 * 3 + y // 3][j]
                graph[x][y] = 0

DFS(0)

seico75 3년 전 1

정답 코드에서는 for i in range(cnt, n, 1): 도 뺐다는 말씀이신거죠?

DFS(cnt)는 cnt 번째 0에 대해서만 1~9 까지 숫자를 넣어보고 cnt+1 번째에 대해서는 다음 재귀함수인 62라인의 DFS(cnt+1)에게 넘겨야 합니다.

그런데 위의 코드는 한번 DFS에 들어가면 모든 n개의 0에 대해서 다 대입을 해보기 때문에 필요이상의 시도를 하게 됩니다.

즉, DFS(0)를 부르면 1번째 0에 대해서 1~9까지 넣어보면서 가능한 경우에 DFS(2)를 불러서 두번째 0에 대해서 시도를 해야하는데..

위 코드는 DFS(0)에서 1번째부터 n번째까지 다 시도를 하고 DFS(1)에서는 2번째부터 n번째까지 또 시도를 합니다.

정답은 각 DFS에서 최대 9번의 시도를 하니 9**n 번 시도를 하는데..

오답(시간초과) 각 DFS에서 cnt * 9 번 시도를 해서 9**n * cnt! 번 시도를 하지 않을까요? (계산이 맞는지.. ㅠㅠ)

당연히 중복된 시도가 많은거구요.

seico75 3년 전 1

정정합니다. 중복된 시도가 아니라 잘못된 시도네요.. DFS(0)에서 i=cnt 외의 경우는 앞의 숫자를 다 0으로 두고 채우니 오답이 나올 수도 있을 것 같은데요..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

고수님들 차이점을 모르겠는데 부탁드립니다.

jin03114 3년 전 0

seico75 3년 전 1

seico75 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말