[백준] 2637번: 장난감 조립 | Python

2637번: 장난감 조립

 

틀린 이유

1. 처음엔 dp[7]로 제출했다. (멍청...)

2. N개의 노드가 주어졌을 때, 기본 부품, 중간 부품을 거쳐 완제품이 되는 노드가 N번임을 가정하고 다이내믹 프로그래밍으로 풀었다. (dp[N]=1 에서 시작)

 

 

정답 코드

각 노드 간 선후관계를 생각해야 할 땐 위상 정렬을 사용한다.

위상 정렬된 topology[N-1]가 완제품 노드임을 이용해 다시 다이내믹 프로그래밍으로 풀었다. 완제품부터 기본부품까지 탑다운(?)으로 접근했다.

 

 

* 최적화 안 돼 있음 주의 *

import sys;input=sys.stdin.readline
from collections import deque
N=int(input())
M=int(input())
next=[[] for i in range(N + 1)]
need=[[] for i in range(N + 1)]
dp=[0]*(N+1)
indegree=[0]*(N+1)
for i in range(M):
    x,y,k=map(int,input().split())
    next[y].append(x)
    need[x].append((y, k))
    indegree[x]+=1

# topology sort
q=deque()
for i in range(1,N+1):
    if indegree[i]==0:
        q.append(i)

topology=[]
while q:
    tmp=q.popleft()
    topology.append(tmp)

    for i in next[tmp]:
        indegree[i]-=1
        if indegree[i]==0:
            q.append(i)

# dp
dp[topology[N-1]]=1
for i in range(N-1,-1,-1):
    node=topology[i]
    for tar,cnt in need[node]:
        dp[tar]+=cnt*dp[node]
for i in range(1,N+1):
    if len(need[i])==0:
        print(i,dp[i])