결국 우리가 봐야 하는 건 각각의 기본 부품들이 얼마나 사용 되었는가, 이것이다.
하나의 중간 부품을 만들 때 필요한 부품들이 먼저 선행되어야 한다는 점이 위상 정렬을 사용할 수 있는 조건이 된다.
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로 어떻게 풀지..?
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)}")