2637. 장난감 조립

 

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

✔ 유형 : 위상 정렬

✔ 문제 풀이:  위상 정렬을 이용한 최단거리느낌? 뭐라고해야하지ㅜㅜ

 

백준 Test Case를 분석해봤을 떄,

위의 배열들을 아래의 그래프로 표현 해볼 수 있는데,

 

⬇️코드

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

N = int(input())
M = int(input())

Graph = { i : {} for i in range(1, N+1)} # 이중 딕셔너리!
need = [0 for _ in range(N+1)] # indegree 개수를 센 리스트
indegree = [0 for _ in range(N+1)]
for i in range(M):
    X, Y, K = map(int, input().split())
    
    Graph[X][Y] = K
    need[Y] += 1
    indegree[X] += 1
    
basic_part = list()
for i in range(1, N+1):
    if indegree[i] == 0:
        basic_part.append(i) # i는 인덱스이므로 1 더해서 넣어준다.
        
q = deque([N])
count =[0 for _ in range(N+1)]
count[N] = 1

while q:# 큐는 기본 부품 리스트!!
    node = q.popleft() # 1시작이야!!
    for next,cost in Graph[node].items():        
        need[next] -= 1
        count[next] += cost*count[node]
        if need[next] == 0:
            q.append(next)

for i in basic_part:
    print(i, count[i])
    
#나느 ㄴ위상정렬을 기본부품부터 시작했는데 그렇게하면 범위가 좁혀지면서 기록하기가 힘들었다.
#그래서 인터넷 치팅을했는데, N부터 시작해서 기본 부품까지 계속 비용을 곱하면된다.