개발하는데 다 이유가 있겠지

2637. 장난감 조립

• 위상 정렬(Topological Sort)를 사용해 구현
• 진입 차수(in-degree) 완성품(7번)부터 큐에 추가
• 비용을 저장하는 배열을 선언하고 시작 지점(7번)의 비용을 1로 초기화(나머지는 0)
• 큐에 넣은 것을 빼고 인접한 노드들을 탐색하면서 비용을 갱신
• 갱신한 노드들의 진입 차수를 -1하고 진입 차수가 0인 것을 다시 큐에 추가하고 반복
• cost[목적지] += cost[출발지] * 가중치(비용)
• arr2 배열을 통해 진입 차수가 없는 기본 부품을 판별하여 출력

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
m = int(input())
arr1 = [[] for _ in range(n + 1)]
arr2 = [[] for _ in range(n + 1)]
indegree = [-1 for _ in range(n + 1)]
cost = [0 for _ in range(n + 1)]
cost[-1] = 1
deq = deque()

for i in range(0, m):
    start, end, weight = map(int, input().split())
    arr1[end].append((start, weight))
    arr2[start].append((end, weight))

for i in range(1, n + 1):
    indegree[i] = len(arr1[i])

deq.append(n)

while deq:
    cur_node = deq.popleft()
    print(cur_node)
    for i in arr2[cur_node]:
        x, y = i
        cost[x] += cost[cur_node] * y
        indegree[x] -= 1
        if indegree[x] == 0:
            deq.append(x)

for i in range(1, n + 1):
    if not arr2[i]:  # 해당 부품을 만드는데 필요한 부품이 없으면, 즉 기본 부품이면
        print(i, cost[i])  # 기본 부품으로 판단하여 출력