2022.02.17 [백준] (python 파이썬) ACM Craft

 

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

1005번: ACM Craft

---

풀이

해당 문제는 위상 정렬에 다이나믹 프로그래밍을 같이 사용해야 하는 문제이다.

왜냐하면 각 건물과의 연결을 생각해야하고 이 때 각 건물까지의 거리를 계산해야 한다.

여기서 건물까지의 거리를 계산할 때 다이나믹 프로그래밍을 이용하여 배열에 저장하고

이전에 나왔던 값이 필요 할땐 다시 계산할 필요없이 저장된 값을 가져오게 해야 하기 때문이다. 

import sys
from collections import deque
 
input=sys.stdin.readline
 
for _ in range(int(input())):
    n,k=map(int, input().split())
    #각 건물마다 짓는 딜레이 저장하기 위한 배열
    #0을 앞에 넣어주고 extend로 추가하는 이유는
    #인덱스를 건물의 숫자와 맞추기 위해 0번째의 인덱스에
    #0을 넣고 1번 인덱스부터 데이터 추가
    delay=[0]
    delay.extend(list(map(int,input().split())))
    #각 건물과 연결된 건물을 저장하기 위한 리스트
    graph=[[] for i in range(n+1)]
    #처음부터 해당 건물까지 짓기 위한 시간을 저장할 리스트
    distance=[0]*(n+1)
    #해당 건물 이전에 지어야 할 건물 수 카운트
    check=[0]*(n+1)
    for i in range(k):
        x,y=map(int,input().split())
        graph[x].append(y)
        check[y]+=1
    taget=int(input())
 
    deq=deque()
    for i in range(1,n+1):
        if check[i]==0:
            deq.append(i)
            #check[i]가 0이면 이전에 지어야 하는 건물이
            #없기 때문에 거리는 해당 건물의 딜레이 시간과 같음
            distance[i]=delay[i]
    while deq:
        a=deq.popleft()
        #taget건물이 pop된건 지어진것을 뜻하므로 break
        if a==taget:
            break
        for i in graph[a]:
            #i의 거리가 0이면 처음 방문하기 때문에 거리는 
            #이전 건물의 거리 + 현재 건물의 딜레이
            if distance[i] == 0:
                distance[i] = distance[a] + delay[i]
            #해당 건물의 거리가 0이 아니면 이미 방문했다는 의미이다.
            #여기서 해당 건물이 짓기 위해서는 이전에 연결된 건물들을 
            #모두 지어야 하므로 저장된 거리와 다른 연결된 거리를 비교하여
            #큰 값을 저장
            else:
                distance[i] = max(distance[i], distance[a] + delay[i])
            check[i]-=1
            if check[i]==0:
                deq.append(i)
    print(distance[taget])