2637번: 장난감 조립

맞은 풀이. 위상 정렬을 이용한 풀이

결국 우리가 봐야 하는 건 각각의 기본 부품들이 얼마나 사용 되었는가, 이것이다.

하나의 중간 부품을 만들 때 필요한 부품들이 먼저 선행되어야 한다는 점이 위상 정렬을 사용할 수 있는 조건이 된다.

indegree가 아닌 outdegree로 접근할 것. 아니면 그래프의 방향만 뒤바꿔서 indegree를 계산할 것.

• 상위 부품 A가 하위 부품 B를 가리키는 간선에서의 가중치를 A를 만들기 위해 필요한 B의 개수로 본다.

• 각 부품마다 cost를 지정한다. 이 cost는 상위 부품을 만들기 위해 자신이 사용된 횟수와 같다.

  부품 A의 cost = sum(상위 부품의 cost * 그 상위 부품을 만들기 위해 필요한 A의 갯수)

# 위상 정렬로 어떻게 풀지..?
# dp로 어떻게 풀지..?

import sys
from collections import deque

def topology_sort():
    queue = deque()
    for i in range(1, node_num+1):
        if indegree[i] == 0:
            queue.append(i)
    
    while queue:
        node = queue.popleft()
        for adj, cost in graph[node]: # graph[start] = (adj, cost)
            val = 1 if costs_list[node] == 0 else costs_list[node] # 완제품의 cost를 1로 잡고
            costs_list[adj] += val * cost  # cost 계산
            indegree[adj] -= 1
            if indegree[adj] == 0:
                queue.append(adj)

if __name__=='__main__':
    input = sys.stdin.readline

    node_num = int(input())
    edge_num = int(input())

    graph = [[] for _ in range(node_num + 1)]
    indegree = [0] * (node_num + 1)
    costs_list = [0] * (node_num + 1)  # 각 노드 값이 사용된 횟수

    for i in range(edge_num):
        start, end, num = map(int,input().split())
        graph[start].append((end, num))
        indegree[end]+=1

    topology_sort()

    for i in range(1,node_num+1):  # 그래프에서 indegree가 0인, 즉 기본 부품들
        if graph[i] == []:
            print(i, costs_list[i])

틀린 풀이. dp를 이용한 풀이

• 반례

반례를 깨기 위해서는 결국 중간 부품을 정렬 시 입력받은 순서나 크기 오름차순이 아닌, 필요한 순서에 따라(먼저 나온 중간 부품을 만들기 위해서 아직 나오지 않은 중간 부품이 필요하면 안 된다) 정렬되어야 한다. 즉, 위상 정렬을 사용해야 한다는 뜻.

# 위상 정렬로 어떻게 풀지..?
# dp로 어떻게 풀지..?

import sys

if __name__=='__main__':
    input = sys.stdin.readline

    node_num = int(input())
    edge_num = int(input())

    dp = [[] for _ in range(node_num+1)]
    lst = []

    basic_parts = set(range(1,node_num+1))  # 중복 방지!
    middle_parts = set()

    for i in range(edge_num):
        lst.append(list(map(int,input().split())))
        middle_parts.add(lst[-1][0])

    print(lst)
    print(middle_parts)

    basic_parts = list(basic_parts - middle_parts) # 전체에서 입력받은 중간부품을 빼면 기본부품
    lst.sort()
    print(basic_parts)

    for i in basic_parts:
        dp[i] = [i]

    for i in range(node_num+1):
        idx, parts, num = lst[i]
        for _ in range(num):
            dp[idx].extend(dp[parts])

    for i in basic_parts:
        print(f"{i} {dp[node_num].count(i)}")