[Baekjoon] 1005번 : ACM Craft(Python, 위상 정렬, DP)

[Baekjoon] 1005번 : ACM Craft(Python, 위상 정렬, DP)

 

목차

 

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

1005번: ACM Craft

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Python

 

방법 1 - 메모리 34032KB / 시간 1532ms / 코드 길이 773B

 

본 문제는 문제만 봐도 위상정렬이라는 느낌이 물씬 풍겼다.

그러나 차이점은 건설 시간이라는 것이 존재하고 이것에 대한 중복 시간 재생, 그리고 최종적으로 목적으로 하는 건물이 지어질 때까지의 시간을 구해야 한다는 점이다.

 

초기에는 graph에 저장해놓은 list를 기반으로 indegree를 처리할 때 time을 계산하는 것이었지만 이렇게 처리할 경우 여러 방향에 대한 값들에 대해 시간 처리가 어렵다는 문제가 있다.

이에 고안한 것은 dp와 같은 시간 처리이다.

dp는 memorization을 바탕으로 점화식을 구하는 것인데 각 노드별 time을 기반으로 해당 노드에서 처리해야 하는 최대 시간을 구할 수 있다. 이 부분만 살짝 수정한다면 문제 solve

 

 

from collections import deque
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, k = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    indegree = [0]*(n+1)
    time = [0] + list(map(int, input().split()))
    dp = [0 for _ in range(n+1)]

    for i in range(k):
        a, b = map(int, input().split())
        graph[a].append(b)
        indegree[b] += 1

    q = deque()

    for i in range(1, n+1):
        if indegree[i] == 0:
            q.append(i)
            dp[i] = time[i]

    while q:
        now = q.popleft()
        for i in graph[now]:
            indegree[i] -= 1
            dp[i] = max(dp[now]+time[i], dp[i])
            if indegree[i] == 0:
                q.append(i)

    idx = int(input())
    print(dp[idx])