[백준] 2637번 장난감 조립 파이썬 코드

코드

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

n = int(input()) # 노드
m = int(input())
graph = [[] for _ in range(n+1)]
indegree = [0]*(n+1)
res = [0]*(n+1)
for _ in range(m):
  x,y,k = map(int, input().split()) # x 완성, y 기본, k 필요한 개수
  graph[x].append((y,k))
  indegree[y] += 1
res[n] = 1
origin = [] # 기본 부품을 넣어줄 리스트
def topological_sort():
  queue = deque([n])
  for i in range(1, n+1):
    # 그래프 해당 노드에 포함된 값이 없으면 기본 부품
    if not graph[i]: origin.append(i)
  while queue:
    popnum = queue.popleft()
    for part,count in graph[popnum]:
      res[part] += count*res[popnum] # 필요한 개수와 파츠를 곱해준다
      # 완제품부터 내려오므로 기본 부품의 개수를 구할 수 있다
      indegree[part] -= 1 # 전입차수 -1
      if indegree[part] == 0:
        queue.append(part)
topological_sort()
for i in origin:
  print(i, res[i]) # 기본부품 출력

dp 테이블을 구성하면서 고민을 많이 했던 문제. 반대로 구성하면 쉬웠을텐데 너무 어렵게 생각했었다.