[백준][Python] 1005번 ACM Craft - 코팩

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

1005번: ACM Craft

풀이

문제를 읽고나서 위상정렬 알고리즘임을 어렵지않게 알 수 있었다.

 

최소 건설 시간을 측정하기 위해 다이내믹 프로그래밍을 사용할 것이다.

건물 완성까지의 최소 시간을 구하기 위해서는 다음과 같은 말이 성립된다.

 

- 선행 건설 되어야하는 건물이 존재한다면 후행 건설을 실시 할 수 없다.

- 이를 위해서는 선행 건설 되어야하는 건물이 모두 건설되어야 한다는 얘기이다.

- 선행 건설이 없는 건물들은 동시에 건설을 실시 할 수 있다.

- 선행 건물 중 소요시간이 소요시간이 가장 긴 건물까지 건설되어야 후행 건설이 가능하다.

- 그렇기에 선행 건설 중 최대 시간이 dp로 넘어간다.

 

코드

# 1005번 ACMcraft
import sys
from collections import deque

t = int(input())
for _ in range(t):
    n, k = map(int, sys.stdin.readline().split())
    cost = list(map(int, sys.stdin.readline().split()))
    graph = [[] for _ in range(n)]
    numOfEdges = [0 for _ in range(n)]
    for _ in range(k):
        a, b = map(int, sys.stdin.readline().split())
        graph[a-1].append(b-1)
        numOfEdges[b-1] += 1
        
    fin_node = int(sys.stdin.readline())
    queue = deque([])

    dp = [0 for _ in range(n)]
    
    for i in range(n):
        if numOfEdges[i] == 0:
            queue.append(i)
            dp[i] = cost[i]

    while queue:
        c_n = queue.popleft()
        for i in graph[c_n]:
        	# 선행 건설되어야 하는 모든 건물이 건설되어야하기에 최대시간을 dp에 넣어준다.
            dp[i] = max(dp[i], dp[c_n] + cost[i])
            numOfEdges[i] -= 1
            if numOfEdges[i] == 0:
                queue.append(i)

    print(dp[fin_node-1])

 

출력결과