백준 2637 장난감 조립(python)

문제 URL : https://www.acmicpc.net/problem/2637

 

 

 

 

 

 

문제 접근법: 

위상정렬 문제입니다.

n이 완성품이고

n에서 출발해서 어떤 조립품이 있는지 확인합니다.

물론 indegree를 줄여가면 탐색해야겠지만

outdegree가 없는것이 기본 부품이기때문에

outdegree가 없는것도 확인해줘야 기본부품만 출력할수있습니다.

 

소스코드 : 

from collections import deque
n= int(input())
m = int(input())
adj = [[] for i in range(n+1)]
indegree =[0]*(n+1)
outdegree =[0]*(n+1)
res = [0]*(n+1)
for i in range(m):
    a,b,c =map(int,input().split())
    adj[a].append((b,c))
    indegree[b]+=1
    outdegree[a]+=1

q =deque()
q.append(n)
res[n]=1
while q:
    cur = q.popleft()
    for i in range(len(adj[cur])):
        next = adj[cur][i][0]
        indegree[next]-=1
        nextcost =  res[cur]*adj[cur][i][1]
        res[next]+=nextcost
        if indegree[next]==0:
            q.append(next)
for i in range(1,n):
    if outdegree[i]==0:
        print('{} {}'.format(i,res[i]))

 

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.