BOJ - 1005

백준 문제 링크
ACM Craft

❓접근법

1. 위상 정렬을 활용했다.
2. 모든 선후 관계를 지키는 전체 순서 계산은 쉬운데,
   건물을 건설하는데 소요되는 시간 구하는 것은 조금 어렵다.
   테스트 케이스 2번을 그림으로 표현하면 아래 그림과 같다.
   
3. 2번 건물의 경우 다 지으려면 30초가 필요하고,
   3번 건물의 경우 다 지으려면 11초가 필요하다.
   이렇게 건물의 경우마다 소요 시간을 다르게 해야하는 점을 주의하자.
4. 먼저 위상 정렬 함수를 만들건데,
   소요 시간을 저장할 answer = [0] * (n + 1)을 만든다.
   그리고 진입 차수가 0인 것부터 큐에 넣고,
   answer[i] = data[i]로 지정한다. # 진입 차수가 0인 것의 시간을 넣었음
5. 큐가 비어있을 때까지 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을
   그래프에서 제거하고, answer를 갱신한다.

for i in graph[now]:
	indegree[i] -= 1
    answer[i] = max(answer[i], answer[now] + data[i])

그리고 진입 차수가 0이 된 노드를 큐에 넣는다.
마지막으로 answer를 return 하면서 함수를 마무리한다.
6. 위상 정렬 함수를 실행하고 건설해야 할 건물의 번호를 출력하면 끝!

👌🏻코드

from collections import deque

def topology_sort():
        answer = [0] * (n + 1)
        queue = deque()
        for i in range(1, n + 1):
            if indegree[i] == 0:
                queue.append(i)
                answer[i] = data[i]

        while queue:
            now = queue.popleft()

            for i in graph[now]:
                indegree[i] -= 1
                answer[i] = max(answer[i], answer[now] + data[i])

                if indegree[i] == 0:
                    queue.append(i)

        return answer
    
t = int(input())
  
for _ in range(t):
    n, k = map(int, input().split())

    data = [0] + list(map(int, input().split()))

    graph = [[] for _ in range(n + 1)]

    indegree = [0] * (n + 1)

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

    w = int(input())
    print(topology_sort()[w])