[백준 2024/09/24] 2637번 장난감 조립

1. 문제

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

 

2. 접근 방법

이번 문제는 정석적인 위상 정렬에서, 개수가 포함된 문제이다.

 

part_need라는 2차원 리스트를 구성하고, 이를 통해서 위상 정렬 동안 계산이 되는 결과를 저장해 주었다.

inDegree가 없는 것부터 접근하여, 마지막까지 계산을 진행하기 때문에, 필요한 부품에 대한 정보가 순차적으로 저장이 되게 된다.

 

만약 5번 부품이 2번 부품 3개를 필요로 하게 된다면 2번 행에 * 3을 한 idx 값을 5번 행에 더해주었다.

 

3. 코드

from collections import deque
from collections import defaultdict
def machine():
    dq = deque()
    base = []

    for i in range(1, n+1, 1):
        if in_degree[i] == 0:
            dq.append(i)
            base.append(i)

    for b in base:
        part_need[b][b] = 1

    for _ in range(n):
        new_i = dq.popleft()

        for i, k in adj[new_i]:
            in_degree[i] -= 1

            for j in range(1, n+1, 1):
                part_need[i][j] += part_need[new_i][j] * k

            if in_degree[i] == 0:
                dq.append(i)

    for i in range(len(part_need)):
        print(part_need[i])
    print()
    print()

    for i in range(len(part_need[n])):
        if part_need[n][i] != 0:
            print("%d %d" %(i, part_need[n][i]))


if __name__ == "__main__":
    n = int(input())
    m = int(input())

    adj = [[] for i in range(n+1)]
    in_degree = [0] * (n+1)
    part_need = [[0] * (n+1) for _ in range(n+1)]

    for i in range(m):
        x, y, k = map(int, input().split())
        adj[y].append([x, k])
        in_degree[x] += 1

    machine()