파이썬 백준 2637 장난감 조립

import sys input = sys.stdin.readline from collections import deque n = int(input()) m = int(input()) basic = [True for i in range(n + 1)] parent = [0 for i in range(n)] V = [[] for i in range(n + 1)] for i in range(m) :     p, c, k = map(int, input().split())     V[p].append([c, k])     basic[p] = False     parent[c] = parent[c] + 1 table = [0 for i in range(n)] que = deque() for i in range(1, n) :     if parent[i] == 0 :         que.append([i, 0]) que.append([n, 1]) while que :     c, k = que.popleft()     for nextc, nextk in V[c] :         table[nextc] = table[nextc] + k * nextk         parent[nextc] = parent[nextc] - 1         if parent[nextc] == 0 :             que.append([nextc, table[nextc]]) for i in range(1, n) :     if basic[i] :         print(i, table[i])

각 부품에 대해 그것을 재료로 만들 수 있는 상위부품의 갯수(=부모)를 parent에 기록한다.

만약 완성품 n이 아닌데 parent가 0인 부품이 있다면 쓸모가 없는 부품이니 큐에 0개를 넣어 제거한다.

완성품 n 1개를 분해하기 위해 que에 [n, 1]을 넣는다.

현재 큐에서 pop된 부품을 중간부품 여러개로 분해한 결과를 table에 기록하고, 그 중간부품들의 parent를 -1한다.

처음에는 [n, 1](1개의 부품n)이 레시피대로 분해되며 그 중간부품중 몇개의 parent가 0이 될 것이다.

각 중간부품이 parent가 0인 상태라면, 상위부품 분해로 인해 갯수가 추가되는 일이 더이상 없다.

이때 que에 넣어 그 부품을 분해하는 것을 반복하면 위상정렬된 순서로 중간부품이 분해된다.

기초부품 단위까지 분해되어 while문이 끝났을 때, 미리 기록해둔 기초부품의 리스트에 있는 부품들만 table에서 골라 출력한다.