글 읽기 - 1005번 질문 드립니다. (Python3/런타임 에러/재귀(BFS))

ohyuni 4년 전 0

안녕하세요.

1005번 질문글 살피며 계속 고쳐보다 막혀서 질문 드립니다.

BFS 재귀 형식으로 풀었고 maximum recursion depth exceeded 에러가 발생합니다.

어떻게 하면 recursion depth를 줄일 수 있을지 조언 부탁드립니다.

혹시 다른 문제가 있는 경우에도 조언 남겨주시면 고맙겠습니다.

코드 첨부합니다.

감사합니다.

import sys

# D: 각 건물당 건설에 걸리는 시간
# order: 건설 순서 (dictionary)
#        order[W]는 W번째 건물을 건설하기 위해 건설해야 하는 건물의 list
# W: 건물의 번호
# time: dynamic programming 결과 저장용 list
#       time[W]는 W번째 건물을 건설에 걸리는 시간
def dp(D, order, W):
    if time[W-1] != -1:
        return time[W-1]
    if not order[W]:
        time[W-1] = D[W-1]
    else:
        max_value = 0
        for i in order[W]:
            max_value = max(dp(D, order, i), max_value)
        time[W-1] = D[W-1] + max_value
    return time[W-1]

for _ in range(int(sys.stdin.readline())):
    N, K = map(int, sys.stdin.readline().split())
    D = list(map(int, sys.stdin.readline().split()))
    order = {key: [] for key in range(1, N+1)}
    for _ in range(K):
        X, Y = map(int, sys.stdin.readline().split())
        order[Y].append(X)
    W = int(sys.stdin.readline())
    time = [-1] * N
    print(dp(D, order, W))

whdgurclzls 4년 전 1

파이썬 recursion 기본 깊이가 1000이라서

sys.setrecursionlimit(10**6) 이렇게 선언해줘서 사용 가능한 recursion depth를 늘리는 방법도 있습니다

ohyuni 4년 전 0

@whdgurclzls 감사합니다!! 덕분에 해결했어요.

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

문제

문제

출처

ICPC

1005번 질문 드립니다. (Python3/런타임 에러/재귀(BFS))

ohyuni 4년 전 0

whdgurclzls 4년 전 1

ohyuni 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말