[백준/Python] 1005번 ACM Craft

문제

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

풀이

import sys
from collections import deque

input = sys.stdin.readline
def solve():
    n, k = map(int, input().split())
    D = list(map(int,input().split()))
    g = {}
    memo = [0] * n
    answerlist = [0] * n
    for i in range(k):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        if x not in g:
            g[x] = []
        g[x].append(y)
        memo[y] += 1

    last = int(input())
    last -= 1
    queue = deque()

    for i in range(n):
        if memo[i] == 0:
            queue.append(i)
            answerlist[i] = D[i]

    while queue:
        cur = queue.popleft()
        if cur in g:
            for next in g[cur]:
                memo[next] -= 1
                answerlist[next] = max(answerlist[next], answerlist[cur] + D[next])
                if memo[next] == 0:
                    queue.append(next)
    print(answerlist[last])
                    
        
t = int(input())

for i in range(t):
    solve()

 

위상정렬을 이용한 풀이입니다. 

memo 리스트의 각 노드의 진입차수를 기록하고 진입차수 0의 노드를 큐에 삽입합니다. 

큐에서 노드를 하나씩 빼며 노드가 갈 수 있는 노드들의 진입 차수를 1씩 줄이며 max(answerlist[next], answerlist[cur] + D[next])을 기록합니다.