[알고리즘 문제풀이][파이썬] 백준 # 2637 장난감조립

예제 입력

첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주어지고, 그 다음 M개의 줄에는 어떤 부품을 완성하는데 필요한 부품들 간의 관계가 3개의 자연수 X, Y, K로 주어진다. 이 뜻은 "중간 부품이나 완제품 X를 만드는데 중간 부품 혹은 기본 부품 Y가 K개 필요하다"는 뜻이다. 두 중간 부품이 서로를 필요로 하는 경우가 없다.

7
8
5 1 2
5 2 2
7 5 2
6 5 2
6 3 3
6 4 4
7 6 3
7 4 5

예제 출력

하나의 완제품을 조립하는데 필요한 기본 부품의 수를 한 줄에 하나씩 출력하되(중간 부품은 출력하지 않음), 반드시 기본 부품의 번호가 작은 것부터 큰 순서가 되도록 한다. 각 줄에는 기본 부품의 번호와 소요 개수를 출력한다.
정답은 2,147,483,647 이하이다.

1 16
2 16
3 9
4 17

DFS로 풀 수 있지 않을까 했었는데 시간초과가 났다..

틀렸던 풀이

import sys
input = sys.stdin.readline

def dfs(part, count):
    global answer
    if part in rqrmnts:
        for req_part, req_count in rqrmnts[part]:
            dfs(req_part, count * req_count)
    else:
        answer[part] += count

n = int(input().rstrip())
m = int(input().rstrip())
rqrmnts = {}
for _ in range(m):
    x, y, k = map(int, input().split())
    if x not in rqrmnts:
        rqrmnts[x] = []
    rqrmnts[x].append((y, k))

answer = [0] * (n+1)
dfs(n, 1)

for i in range(1, n):
    if answer[i]:
        print(i, answer[i])

위상정렬을 통한 문제풀이

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

n = int(input().rstrip())
m = int(input().rstrip())
adj = [[] for _ in range(n + 1)]
parts_needed = [[0] * (n + 1) for _ in range(n + 1)]
q = deque()
degree = [0] * (n + 1)
for _ in range(m):
    a, b, c = map(int, input().split())
    adj[b].append((a,c))
    degree[a] += 1

for i in range(1, n + 1):
    if degree[i] == 0:
        q.append(i)

while q:
    now = q.popleft()
    for next, next_parts_needed in adj[now]:
        # 기본 부품
        if parts_needed[now].count(0) == n + 1:
            parts_needed[next][now] += next_parts_needed
        # 중간 제품
        else:
            for i in range(1, n + 1):
                parts_needed[next][i] += parts_needed[now][i] * next_parts_needed
                
        degree[next] -= 1
        if degree[next] == 0:
            # 차수 0아면 큐에 넣음
            q.append(next)

for parts in enumerate(parts_needed[n]):
    if parts[1] > 0:
        print(*parts)

알고리즘문제 풀이 모음:
github.com/whwogur/BOJ