BOJ 1005: ACM Craft

오늘의 문제는 ACM Craft이다.

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

t=int(input())
for _ in range(t):
    n,k=map(int,input().split())
    time=[0]+list(map(int,input().split()))
    adj=[[] for _ in range(n+1)]
    degree=[0]*(n+1)
    answer=[0]*(n+1)
    for _ in range(k):
        a,b=map(int,input().split())
        adj[a].append(b)
        degree[b]+=1
    w=int(input())
    q=deque()
    for i in range(1,n+1):
        if degree[i]==0:
            q.append(i)
            answer[i]=time[i]
    while q:
        a=q.popleft()
        if a==w:
            break
        for b in adj[a]:
            answer[b]=max(answer[b], answer[a]+time[b])
            if degree[b]==1:
                q.append(b)
            degree[b]-=1
    print(answer[w])

이 문제를 풀기 위해서 도착지점부터 bfs도 써봤지만, 결과적으로 '위상 정렬' 알고리즘을 사용하여 문제를 풀었다.

 

우선, t개의 케이스에 대해서 문제를 풀어야 하기 때문에 for 문에 들어간다.

그 이후, 건물의 개수 n, 길들의 개수 k를 input 받고,

각 건물을 짓는데 걸리는 시간을 time 이라는 list 안에 저장한다.

adj는 건물들 간의 연결 관계,

degree는 위상,

answer는 각 건물까지 걸리는 최대 거리이다.

여기서 위상이란, 몇 개의 길의 끝에 연결되어있는지로서,

이 문제 같은 경우에는 모든 길과 연결이 되어야 결국에 다음 건물을 지을 수 있기 때문에,

모든 길과 연결이 완료되었는지를 명시해준다.

결국 k개의 길로 연결되는 정보를 adj에 저장할 때, degree를 통해 값을 증가시키면서 연결 관계가 저장되는 것이다.

 

여기서 degree의 값이 0이라 함은, 시작점이라는 것이다. (전에 세워야할 건물이 없다)

그렇기 때문에, answer에 그 건물을 짓는 시간만 저장하면 될 것이다.

while문을 통해서, 목표 건물을 세울 때 까지, 기존 time 과 새로운 길로 이루어지는 time을 비교하고, degree를 낮춰가며

해결한다.