[백준/BOJ] 1005번 - ACM Craft (Python)

 

· 문제링크

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

1005번: ACM Craft

· 핵심 : 위상 정렬 + DP

 

---

· 코드(Python)

# https://www.acmicpc.net/problem/1005
t = int(input())
for _ in range(t):
    N, K = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    ind = [0 for _ in range(N + 1)]
    dp = [0 for _ in range(N + 1)]
    times = ['인덱스용'] + list(map(int, input().split()))
    for _ in range(K):
        X, Y = map(int, input().split())
        adj[X].append(Y)
        ind[Y] += 1
    W = int(input())
    # 후보군 넣기
    candidates = []
    for num in range(1, N + 1):
        if ind[num] == 0:
            candidates.append(num)
            dp[num] = times[num]
    # candidates 비울 때까지 확인
    result = []
    while candidates:
        cur = candidates.pop()
        result.append(cur)
        
        for nxt in adj[cur]:
            ind[nxt] -= 1
 
            dp[nxt] = max(dp[nxt], times[nxt] + dp[cur])
            if ind[nxt] == 0:
                candidates.append(nxt)

    print(dp[W])