[위상 정렬] 백준 1005번 : ACM Craft / 골드 3 *

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

1005번: ACM Craft

import sys
import collections
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
    n, k = map(int, input().split())
    times = list(map(int, input().split()))

    deg = [0 for _ in range(n)]
    graph = collections.defaultdict(list)

    for _ in range(k):
        a, b = map(int, input().split())
        graph[a].append(b)
        deg[b-1] += 1

    target = int(input())

    q = collections.deque()
    for i in range(n):
        if deg[i] == 0:
            q.append(i+1)

    sum_times = [times[i] for i in range(n)]

    while q:
        cur = q.popleft()
        if cur == target:
            break
            
        for next in graph[cur]:
            sum_times[next - 1] = max(sum_times[next - 1], sum_times[cur - 1] + times[next - 1])
            deg[next-1] -= 1
            if deg[next-1] == 0:
                q.append(next)

    print(sum_times[target-1])

위상 정렬 알고리즘이 사용되지만 그것만으로는 문제를 풀 수 없다.

 

처음 시도했던 방법은 while 문안에 len(q)만큼 반복문을 돌려서 각 반복마다 가장 큰 시간 값을 취해서 result라는 결과에 더해주는 방식이었는데 이러면 반례에 막혀버린다.

 

내가 생각하지 못했던 반례의 예시는 다음과 같다.

4 3
10 10 10 100
1 2
2 3
4 3
3

이 경우 답은 110이다. 

 

그래서 개선한 방법은 누적된 시간 정보를 담고 있는 sum_times 리스트를 만들어서 이곳에

현재 노드(포함)까지 소요되는 누저 시간의 최댓값을 저장해주는 것이다.

dp 방식과 유사하다. 

 

결론적으로 위상정렬 + dp 이기 때문에 생각하기가 어려웠다. 체감 난이도는 골드3보단 어려운 것 같다.