[백준] 장난감 조립

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

2637번: 장난감 조립

위상정렬과 DP를 함께 수행하는 문제입니다. 골드 2문제라서 그런지 난이도가 꽤 있었습니다. 단순히 위상정렬만 실행을 하면 메모리 초과가 떠서 DP까지 함께 수행을 해줘야합니다. 먼저 기초 부품들을 따로 저장해두고 각 부품별 필요한 기초 부품들을 dp 배열에 저장해둡니다. dp[i][j]는 j를 만들기 위한 i번째 기초 부품의 개수를 저장하고 있습니다. 위상정렬을 해주면서 각 부품에 필요한 기초 부품의 수를 저장해두고 in_node가 0이 되는 순간이 곧 필요한 기초 부품 수 계산이 끝난 것을 의미하므로 큐에 넣어줍니다.

 

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

graph = defaultdict(list)
n = int(input())
m = int(input())


in_node = [0] * (n + 1)
element = []

for _ in range(m):
    # x를 만들기 위해 y가 k개 필요하다.
    x, y, k = tuple(map(int, input().split()))
    graph[y].append((x, k))
    in_node[x] += 1

# in_node가 0인 애들은 기초 부품이다.
for i in range(1, n + 1):
    if in_node[i] == 0:
        element.append(i)


# dp[i][j]:j를 만들기 위해 필요한 i의 개수
dp = [
    [0] * (n + 1)
    for _ in range(len(element))
]

# 기초 부붐들을 세팅한다.
for idx, el in enumerate(element):
    dp[idx][el] += 1

q = deque([el for el in element])

while q:
    cur = q.pop()
    # 다음 노드를 만들기 위해 필요한 개수
    for next, cnt in graph[cur]:
        # next를 만들기 위해 필요한 i번째 기초 원소를 저장한다.
        for i in range(len(element)):
            dp[i][next] += cnt * dp[i][cur]

        in_node[next] -= 1

        if in_node[next] == 0:
            q.append(next)

for i in range(len(element)):
    print(element[i], dp[i][n])