백준 2637 <장난감 조립> Python

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

---

위상정렬 문제입니다.

 

간단하게 생각해보면 DFS 나 BFS 를 사용해 한 부품씩 곱해 더해주면 될 것 같지만 단계나 부품의 수가 복잡해지고 배수가 늘어나면 시간이나 메모리가 부족해집니다. 그렇기에 조금 더 효율적으로 단계를 진행할 필요가 있습니다.

 

그렇기에 단계별로 개수를 병합해 한번에 곱하는 식으로 진행하면 비교적 효율적으로 진행할 수 있습니다.

위 방법으로 진행할 때 모든 중간부품의 개수를 카운트하지 않았을 때 다음 단계를 계산해버리면 오류가 생기므로 중간부품의 개수가 모두 카운트 될 때 다음 단계로 넘어가야 하는데, 이 때 위상정렬을 사용할 수 있습니다.

 

B 부품을 만들기 위해 A 부품이 필요하다고 할 때(A->B) 'B 부품 노드에 A 부품 노드가 들어오는 노드다' 라고 표현하겠습니다. 들어오는 노드의 수가 양수면 아직 해당 부품의 개수를 모두 카운트 하지 않았기에 큐에 넣지 않고 들어오는 노드의 수가 0 이면 해당 부품의 개수를 모두 카운트했다고 생각할 수 있으므로 다음 노드를 큐에 넣어줄 수 있습니다.

---

import sys
from collections import deque

input = sys.stdin.readline


def solution(N, M, gears):
    # 그래프
    graph = [[] for _ in range(N+1)]
    for x, y, k in gears:
        graph[x].append([y, k])
    
    # 위상 정렬 그래프 / [들어오는 노드의 수, 나가는 노드의 수]
    topol_list = [[0, 0] for _ in range(N+1)]
    topol_list[0] = [float('inf'), float('inf')]
    for parent, child, _ in gears:
        topol_list[parent][1] += 1
        topol_list[child][0] += 1

    # 필요한 부품의 수
    gears = [0 for _ in range(N+1)]
    gears[N] = 1
    # 큐
    q = deque([N])
    # 순회
    while q:
        # 현재 노드
        now_node = q.popleft()
        # 순회
        for next_node, mul in graph[now_node]:
            # 부품의 수 더해주기
            gears[next_node] += gears[now_node] * mul
            # 다음 노드의 들어오는 노드 빼주기
            topol_list[next_node][0] -= 1
            # 다음 노드의 들어오는 노드가 0 이면 큐에 넣어주기
            if not topol_list[next_node][0]:
                q.append(next_node)
    
    for gear in range(len(gears)):
        if not topol_list[gear][1]:
            print(f'{gear} {gears[gear]}')


# 입력
N = int(input().strip())
M = int(input().strip())
gears = [list(map(int, input().strip().split())) for _ in range(M)]

solution(N, M, gears)