[BOJ/1005] ACM Craft - 풀이 및 코드 (런타임 에러 해결법)

1005번: ACM Craft

문제

풀이

 비슷한 문제인 게임 개발(https://highlaw00-dev.tistory.com/44) 문제를 이미 풀었습니다. 완전탐색의 시간복잡도와 사이클의 유무에 관해 포스팅해두었습니다. 이번 풀이에서는 파이썬의 특징으로 인해 발생하는 런타임 에러에 대해 간략히 다뤄보겠습니다.

 

 재귀적으로 선행 건물의 비용을 구해야하기 때문에 재귀를 여러번 할 가능성이 존재합니다. 백준 채점 서버에서는 파이썬의 최대 재귀 횟수가 1000회로 지정되어 있습니다. 본 문제에서는 최대 재귀 횟수를 증가시켜주지 않으면 런타임 에러(RecursionError)가 발생합니다. 본 문제에서 발생할 수 있는 재귀 함수 호출이 최대 몇번인지 알아보겠습니다.

 

 그래프 탐색 중 DFS 탐색에 대해 알아두고 있으면 최대로 발생할 수 있는 재귀 함수 호출이 몇 번인지 이해하기 쉽습니다. 어떤 건물을 짓기 위해 그 건물이 요구하는 선행 건물의 값을 구하기 위해 재귀하고, 또 그 건물의 요구 선행 건물의 값을 구하기 위해 재귀하고... 이런식으로 재귀를 진행한다고 하면, 건물들의 관계가 다음 그림과 같을 때 재귀 횟수가 가장 크게 됩니다.

 건물의 개수가 1000개 이기 때문에 재귀를 최대 1000번 하게 됩니다. 그런데 왜 인지는 모르겠지만 최대 재귀 호출을 기본값인 1000으로 세팅하면 오류가 발생합니다. 1001로 해주면 런타임 에러가 발생하지 않는데 솔직히 말해서 아직도 왜 이런일이 발생하는지 확인이 되지 않습니다. 코드 상에서 재귀를 1000번 하는 것 같지 않은데 어떤게 문제인지 알고 계신 분께선 댓글 달아주시면 감사하겠습니다!

 

 만약 이런 비슷한 문제에서 N이 1000이상의 값을 가질 수 있게 되면 sys.setrecursionlimit()을 통해 해결하시면 다른 로직상 문제가 없다는 전제하에 통과하실겁니다!

 

코드 

코드 치팅은 BOJ 제재 사유입니다.

import sys
sys.setrecursionlimit(1001)
input = sys.stdin.readline


# root와 연결된 모든 노드에 대해서 DFS 진행


def get_cost(root):
    requirements_cost = 0
    for v in graph[root]:
        if dp[v] == -1:
            dp[v] = get_cost(v)
        requirements_cost = requirements_cost if requirements_cost > dp[v] else dp[v]
    return requirements_cost + costs[root]


t = int(input().rstrip())
for _ in range(t):
    n, k = map(int, input().rstrip().split())
    costs = [0] + list(map(int, input().rstrip().split()))
    # 건설순서 x, y
    # 그래프를 역순으로 설정
    graph = [[] for _ in range(n+1)]
    for _ in range(k):
        x, y = map(int, input().rstrip().split())
        graph[y].append(x)
    w = int(input().rstrip())
    # dp 테이블 초기화
    # dp[i] = i번째 건물을 짓는데 걸리는 최소 시간
    # dp[i] = max(dp[a1] + dp[a2] + ... dp[aj]) + cost[i] || a1,...,aj는 i를 짓기 위해 반드시 지어야하는 건물
    dp = [0] + [-1 for _ in range(n)]

    ans = get_cost(w)
    print(ans)

참고자료

매우 비슷한 문제인 BOJ 1516 게임 개발 문제도 확인해보세요.

[BOJ/1516] 게임 개발 - 풀이 및 코드