[Baekjoon 2637 / python / 골드2] 장난감 조립

from collections import deque

import sys

input = sys.stdin.readline

N = int(input())  # 노드(부품) 개수

E = int(input())  # 간선 개수

indegree = [0 for _ in range(N + 1)]  # 진입차수 담을 리스트

needs = [[0] * (N + 1) for _ in range(N + 1)]  # 부품별 요구부품량 담을 리스트

graph = [[] for _ in range(N + 1)]  # 연결정보 담을 리스트

for _ in range(E):

    leaf, root, money = map(int, input().split())

    graph[root].append([leaf, money])

    indegree[leaf] += 1

def toy():

    queue = deque()

    for i in range(1, N + 1):  # 진입차수 0인 노드들 큐에 삽입(기본부품들)

        if indegree[i] == 0:

            queue.append(i)

    while queue:

        here = queue.popleft()  # 큐에서 노드 빼기

        for next, need in graph[here]:  # 현재노드 인접리스트에 대하여 반복

            if sum(needs[here]) == 0:  # 현재노드가 기본부품일 경우( 기본부품은 요구량이 없다 )

                needs[next][here] += need

            else:  # 현재노드가 중간부품일 경우

                for i in range(1, N + 1): # 중간부품의 모든 필요부품을 훑으며, 완성품의 중간부품 필요량만큼 일일이 곱해서 추가해준다

                    needs[next][i] += needs[here][i] * need

           

            indegree[next] -= 1  # 간선 지우기

            if indegree[next] == 0:  # 간선 지웠는데 진입차수 0 되면 큐에 삽입하기

                queue.append(next)

toy()

for i in range(1, N + 1):

    if needs[N][i] >= 1:  # 완성품의 필요부품 리스트에 기본부품이 존재할 경우 출력 ( 기본부품이 4개가 아닐 수도 있다 )

        print(f'{i} {needs[N][i]}')

 
위상정렬과 DP로 풀 수 있는 문제이다. 난 위상정렬로 해결했다.
 
기본부품, 중간부품, 완성품이 존재한다.
기본부품은 진입차수가 없는 노드. 즉 처음부터 주어지는, 조합으로 만들 수 없는 부품이다.
중간부품은 진입차수가 있으며, 기본부품으로만 이루어지거나 기본부품 + 중간부품으로 이루어진다.
완성품은 기본부품과 중간부품으로 이루어진다.
 
최종적으로 "완성품을 만드는 데 필요한 기본부품의 수"를 출력해야 한다. 물론 중간부품을 만들 때 들어간 기본부품도 포함이다.
원리는 크게 어렵지는 않다. 방향 그래프에 가중치를 넣고, 간선을 하나 지날 때마다 그냥 곱해주면 된다.
근데 이걸 코드로 어떻게 짤 것인가가 문제다... 정말 헷갈리고 골치 아프다.
 
난 graph 리스트에 인접 리스트 형태로 가중치(부품요구량)와 연결정보를 담았고,
needs 리스트에 (N + 1) * (N + 1) 크기로 각 부품의 필요 부품을 전부 담을 수 있게 해서, 한번 노드를 거칠 때마다 더하거나 곱한 값을 그때그때 업데이트했다.
 
기본부품(진입차수가 0인 노드)을 먼저 순회하면서 needs의 중간부품과 완성품 행에 요구량을 입력 후, 기본부품이 아닌 노드에서는 간선을 지날 때마다 기존 값과 요구량을 곱한 후 더해줘야 한다.
말로 설명하기 좀 힘든데 코드와 주석을 함께 보면서 직접 코드를 입력해봐야 이해가 쉬울 거라고 생각한다.
 
정 이해가 안 되면 needs 리스트를 한번 반복 할 때마다 출력하게 해서 진행상황을 보는 것도 괜찮다.