백준 2637 장난감 조립(python)

문제

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

2637번: 장난감 조립

---

위상 정렬과 dp개념을 사용하여 푼 문제입니다. 부품 간의 관계를 파악하여 우선순위를 따라가며 개수들을 계산하는 문제였습니다. 과정은 다음과 같습니다.

• 먼저 입력을 받아 장난감 부품중 기본 부품을 따로 구분해서 큐에 넣어주고 기본 부품부터 순회를 시작합니다. 
• 연결된 상위 부품의 갯수를 계산하기 때문에 필요로 하는 하부 부품들의 개수를 하부 부품들을 만들 때 드는 개수에 곱해서 더해 줍니다. 
• 그 뒤는 기본적인 위상정렬과 비슷하게 방문했다면 진입 차수를 하나 낮춰 줍니다. 그 뒤 진입 차수가 0인 장난감 부품을 방문합니다.
• 최종 부품을 만드는데 드는 기본 부품들의 갯수를 출력합니다.

---

소스코드 

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


N = int(input().rstrip())
M = int(input().rstrip())

arr = [[] for _ in range(N+1)]
ind = [0] * 101  # indegree
v = [[0] * (N+1) for _ in range(N+1)]  # 갯수를 저장할 배열
for i in range(M):
    # cur 만들어야할 부품 prev 사용되는 부품 val 갯수
    cur, prev, val = map(int, input().rstrip().split())
    arr[prev].append((cur, val))  # 만들때 사용하는 부품 기준으로 필요한 부품갯수 저장
    ind[cur] += 1  # 차수 만들어야할 부품

q = deque()

for i in range(1, N+1):
    if ind[i] == 0:  # 차수가 0인 기본 부품에서 시작
        q.append(i)
        v[i][i] = 1  # 기본 부품만 시작값을 1로 할당함


while q:
    here = q.popleft()
    for next in arr[here]:
        for i in range(1, N+1):
            # 다음 부품을 만드는데 필요한 부품 계산, 현재 부품 만드는데 드는 개수에 다음 부품 만들때 필요한 부품 곱해줌
            v[next[0]][i] += next[1]*v[here][i]
            print(v[next[0]][i])
        ind[next[0]] -= 1
        if ind[next[0]] == 0:
            q.append(next[0])


for i in range(1, N+1):
    if v[N][i]:  # 기본 부품 외에 다른건 시작이 0이었기 때문에 세지 않음
        print(f"{i} {v[N][i]}")