python 백준 2637번 장난감 조립

백준 2637번 문제

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

2637번: 장난감 조립

import sys
from collections import deque

## 문제입력을 조금이라도 편하게 받기 위해 배움 동일폴더가 아니면 경로설정이 필요하다 ##
#sys.stdin = open('inputs.text')

num = int(sys.stdin.readline())
index = int(sys.stdin.readline())

## vertex 의 몇개의 간선이 있는지를 check ##
in_degree = [0] * (num+1)

## vertex가 어떤 vertex와 이어져 있는지 인접리스트로 표현 ##
graph = [[] for i in range(num+1)]

## 장난감 기본부품과 중간부품의 코스트르 비교해주기 위함 ##
needs = [[0] * (num + 1) for _ in range(num + 1)]
mini_part = []
for _ in range(index):
    a,b,c = map(int,sys.stdin.readline().split())
    graph[b].append((a,c))
    in_degree[a] += 1
queue = deque()

## 장난감의 간선의 개수가 없으면 최소파트로 저장하면서 queue에 넣어준다 위상정렬의 queue 방식##
for idx in range(1,num):
    if in_degree[idx] == 0:
        mini_part.append(idx)
        queue.append(idx)


while queue:
## 최초 while이 돌때 queue=[1,2,3,4]와 같은 최소단위 부품의 점(vertex)가 들어있다 ##
    now = queue.popleft()
    
## graph[1]에는 (5[1번 vertex가 5번과 연결되어있다.], 2[5번을 만들기위해서 1번 부품 2개가 필요])##
## next = 5가 저장되고 next_cost = 2 가 저장 된다
    for next, next_cost in graph[now]:

## now가 최소부품 단위 일경우 조립과정이 아니기 때문에 입력해준다 ##
        if now in mini_part:
            needs[next][now] = next_cost
            
## 하지만 now가 조립되는 중간 부품일 경우 하위 단위부품들이 필요하여
## 6의 부품을 만들기 위해 3(3개),4(4개),5(2개)부품이 필요하며
## 5부품의 경우 중간부품이기 때문에 5부품의 필요한 1(2개), 2(2개)를 * 2(6을만들기 위해 필요한개수) 해준다
        else:
            for i in range(1,num+1):
                needs[next][i] += needs[now][i] * next_cost

## 업데이트가 끝나고 now의 역할이 끝났기 때문에 now와 연결되있는 vertex의 간선을 줄이며
## update된 vertex의 간선이 0이 되었으면 새롭게 queue에 넣어준다
    for j in graph[now]:
        in_degree[j[0]] -= 1
        if in_degree[j[0]] == 0:
            queue.append(j[0])

for idx in range(1,num+1):
    if needs[num][idx] != 0:
        print(f'{idx} {needs[num][idx]}')

1. 업데이트된 장난감 부품 개수 cost