백준 1005 : ACM Craft

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

1005번: ACM Craft

 

해결 방법 : 위상 정렬

• 그래프 구조에서 주어진 조건에 알맞게 진행되어야 하므로 위상 정렬 문제이다.
• 해당 건물이 건설 되는 시간은 해당 건물의 조건이 되는 건물들 중 최대 소요 시간에 의해 결정되므로, 다음과 같은 점화식으로 해결 할 수 있다.
  • time[next 건물] = max(time[next 건물], time[current 건물] + next 건물 소요시간)
• 어떤 건물의 조건이 되는 모든 건물들이 건설 완료되었다면 해당 건물이 조건이 되는 이후의 건물들을 탐색해야 한다.
  • 건물 X의 조건 건물 개수를 preBuilt에 저장, 건물 X를 next 건물로 참조할 때마다 preBuilt[X]를 1감소시켜준다. 해당 값이 0이 되면 건물 X를 Queue에 push해준다.

 

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

def solution(N, D, linked, preBuilt, W):
    times = [0] * N # 각 건물에 대한 건설 필요시간
    Q = deque([]) # 건설 가능한 건물들

    for node in range(N): # 처음에 건설 가능한 건물들 탐색
        if preBuilt[node] == 0:
            Q.append(node)
            times[node] += D[node]

    while Q:
        cur = Q.popleft() # 현재 건설하려는 건물

        for next_node in linked[cur]: # 현재 건물이 조건이 되는 다음 건물들
            times[next_node] = max(times[next_node], times[cur] + D[next_node]) # 갱신
            preBuilt[next_node] -= 1 # 현재 건물이 건설되었으므로,
            if preBuilt[next_node] == 0: # next 건물의 조건 건물들이 모두 건설됨
                Q.append(next_node) # next 건물을 건설 queue에 추가

    return times[W]

if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N, K = map(int, input().split())
        D = list(map(int, input().split()))
        linked = defaultdict(list)
        preBuilt = defaultdict(int)
        for _ in range(K):
            f, t = map(int, input().split())
            linked[f - 1].append(t - 1)
            preBuilt[t - 1] += 1
        W = int(input()) - 1
        result = solution(N, D, linked, preBuilt, W)
        print(result)