[Baekjoon] Topology Sort - ACM Craft

문제

1005번: ACM Craft

 

풀이

기존 topology_sort에서 현재 지을 수 있는 건물의 cost만 넣어주면 된다.

단, 가장 큰 값을 넣어줘야하므로 이전값과 비교하여 큰 값을 넣어준다.

 

import sys
from collections import deque

t = int(sys.stdin.readline().rstrip())

for _ in range(t):
    n, m = map(int, sys.stdin.readline().rstrip().split())
    cost = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
    indegree = [0 for _ in range(n + 1)]
    graph = [[] for _ in range(n + 1)]

    for _ in range(m):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        graph[x].append(y)
        indegree[y] += 1

    w = int(sys.stdin.readline().rstrip())


    def topology_sort(cost, indegree, graph, w):
        q = deque([])
        result = [0] * (n + 1)

        for i in range(1, n + 1):
            if not indegree[i]:
                q.append(i)
                # 건물을 지을 수 있는 비용
                result[i] = cost[i]
        
        while q:
            now = q.popleft()

            for i in graph[now]:
                # 건물을 지을 수 있는 비용
                indegree[i] -= 1
                result[i] = max(result[i], result[now] + cost[i])

                if not indegree[i]:
                    q.append(i)


        return result[w]


    print(topology_sort(cost, indegree, graph, w))

 

채점 결과