⚔️ 백준

---

📌 2637 장난감 조립

from collections import deque
N=int(input()) # 1~N-1은 부품, N은 완제품
M=int(input()) # edge 개수
bp=[[] for _ in range(N+1)] # 부품들에 필요한 재료
res=[0 for _ in range(N+1)] # 완제품이 필요로 하는 기본 부품들
indegree=[0 for _ in range(N+1)] # 진입차수
queue = deque() # 완제품 만들기 위해 필요한 재료들 (기본 부품이면 그대로 더한다)
for _ in range(M):
    X,Y,K=map(int,input().split()) # X 만들 때 Y가 K개 필요하다
    bp[X].append((Y,K))
for p in bp[N]:
    queue.append(p)
while queue:
    part = queue.popleft()
    Y,K=part[0],part[1]
    if bp[Y]: # Y가 중간 부품이라면
        for p in bp[Y]:
            y,k = p[0], p[1]
            queue.append((y,k*K))
    else: # Y가 기본 부품이라면
        res[Y]+=K
for i in range(1,N):
    if not bp[i]:
        print(i,res[i])

왠지 위상 정렬로 풀기 싫어서 역순으로 탐색해봤는데 메모리 초과남. 큐에 너무 많이 들어가서인듯?

from collections import deque
N=int(input()) # 1~N-1은 부품, N은 완제품
M=int(input()) # edge 개수
bp=[[] for _ in range(N+1)] # 해당 부품이 쓰이는 중간 부품/완제품
res=[[0 for _ in range(N+1)] for _ in range(N+1)] # 중간 부품/완제품이 필요로 하는 기본 부품들
indegree=[0 for _ in range(N+1)] # 진입차수
queue = deque() # 기본 부품부터 시작해서 중간 부품들을 전부 기본 부품들의 조합으로 바꾼다
basic = [] # 기본 부품 리스트
# 부품 조합법을 받는다
for _ in range(M):
    X,Y,K=map(int,input().split()) # X 만들 때 Y가 K개 필요하다
    bp[Y].append((X,K)) # Y가 X에 K개 필요하다
    indegree[X]+=1
# 기본 부품들로만 만들어진 중간 부품들을 큐에 넣는다
for i in range(N):    
    if indegree[i] == 0: # 기본 부품들에서 경로 시작
        basic.append(i) # 기본 부품 리스트에 추가
        for part in bp[i]: # 기본 부품들로 만들어지는 중간 부품들에 대해
            X,Y,K = part[0],i,part[1] # X 만들 때 Y가 K개 필요하다
            res[X][Y] = K
            indegree[X]-=1
            if indegree[X]==0:
                queue.append(X)
# 중간 부품들이 쓰이는 부품들을 차근차근 만들기 시작한다
while queue:
    Y = queue.popleft()
    for part in bp[Y]: # Y가 쓰이는 중간 부품들에 대해
        X,K = part
        for b_part in basic:

위상 정렬로 풀어보려고 했는데 풀이가 너무 어지러워져서 뭔가 아닌 것 같고 100% 어딘가에서 실수해서 틀릴 것 같아서 그냥 로직을 다시 갈아엎기로 함

from collections import deque
N=int(input()) # 1~N-1은 부품, N은 완제품
M=int(input()) # edge 개수
bp=[[] for _ in range(N+1)] # 해당 부품이 쓰이는 중간 부품/완제품
res=[[0 for _ in range(N+1)] for _ in range(N+1)] # 중간 부품/완제품이 필요로 하는 기본 부품들
indegree=[0 for _ in range(N+1)] # 진입차수
queue = deque() # 기본 부품부터 시작해서 중간 부품들을 전부 기본 부품들의 조합으로 바꾼다
basic=[]
# 부품 조합법을 받는다
for _ in range(M):
    X,Y,K=map(int,input().split()) # X 만들 때 Y가 K개 필요하다
    bp[Y].append((X,K)) # Y가 X에 K개 필요하다
    indegree[X]+=1
# 기본 부품 리스트 세기
for i in range(1,N):
    if indegree[i]==0:
        basic.append(i)
# 기본 부품들로부터 시작
for i in range(1,N):
    if indegree[i] == 0:
        for p in bp[i]:
            X,Y,K=p[0],i,p[1]
            res[X][Y]=K
            indegree[X]-=1
            if indegree[X]==0:
                queue.append(X)
# 부품들 조립해서 만들기
while queue:
    Y = queue.popleft()
    for part in bp[Y]: # Y가 쓰이는 중간 부품들에 대해
        X,K = part
        for i in range(N):
            res[X][i]+=res[Y][i]*K
        indegree[X]-=1
        if indegree[X]==0:
            queue.append(X)
# 완제품에 쓰이는 기본 부품 출력
for i in basic:
    print(i,res[N][i])

근데 다시 해봐도 비슷하게 만들어지긴 함.
30몇퍼에서 틀렸습니다 뜸.

# 기본 부품들로부터 시작
for i in basic:
    for p in bp[i]:

??? 최적화나 해보려고 for i in range(1,N)을 for i in basic으로 바꿨더니 맞음.

중간 부품이 순회 도중에 indegree가 0이 돼버리면 꼬여서 그랬는듯.

결과가 탐색 조건에 영향을 주는 것을 조심하기

import sys
input=sys.stdin.readline

이거 추가했더니 52ms에서 48ms로 줄어듦.

for part in bp[Y]: # Y가 쓰이는 중간 부품들에 대해
    X,K = part

이거 대신

for X,K in bp[Y]

이렇게 바로 바꿔도 되는듯.

그리고 기본 부품이랑 중간 부품 돌리는거 나눈 이유가 최적화 때문이었는데

다른 풀이들 보니까 딱히 상관 없는 것 같다.
기본 부품 수가 적어서 그런듯.