백준 2637번: 장난감 조립

위상 정렬에 대한 개념만 살짝 숙지한 나에겐 너무나 어려운 문제였다. 결국 자력으로 풀어내지 못하고 서칭을 좀 했는데, 답안 코드들을 하나하나 뜯어보며 위상 정렬에 대해 조금 더 이해할 수 있었다. 다음은 공부 후 내가 작성해본 코드다.

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

N = int(input())
M = int(input())
inputs = [list(map(int, input().split()))for _ in range(M)]

parts = [[]for _ in range(N+1)]
costs = [[0]*(N+1)for _ in range(N+1)]
inDegree = [0]*(N+1)

for part in inputs:
    parts[part[1]].append((part[0], part[2]))
    inDegree[part[0]] += 1
    
q = deque()
for i in range(1, len(inDegree)):
    if inDegree[i] == 0:
        q.append(i)

while q:
    current = q.popleft()
    for nextPart, nextCost in parts[current]:
        if any(costs[current]):
            for i in range(1, len(inDegree)):
                costs[nextPart][i] += costs[current][i]*nextCost
        else:
            costs[nextPart][current] += nextCost

        inDegree[nextPart] -= 1
        if inDegree[nextPart] == 0:
            q.append(nextPart)

for i in enumerate(costs[N]):
    if i[1] > 0:
        print(*i)

말이 내가 작성한 코드지, 서칭을 통해 알아낸 다른 분의 정답 코드와 거의 흡사하다. ㅠㅠ 공부.. 더 해야겠지? 😂
이 문제를 풀기 전에는 위상 정렬이 생각보다 별거 없다는 생각을 했었다. 그냥 부모 - 자식간의 관계 정리해주는, 뭐 그런거 아니야? 이렇게 생각했었는데. 그렇게만 생각하면 요런 문제를 만났을 때 절대 못풀겠다는 생각이 들었다. 이 정답 코드의 포인트는 각 부품들에(다음 부품, 갯수)를 기록하고 처리하는 부분인 것 같다. 이렇게 함으로써 말단 자식부터 큐에 넣었다가 빼는 작업들을 거치며, 부모의 필요 부품들을 갱신해나가는 부분이 정말 아름답다고(?) 느껴졌다. ㅋㅋㅋㅋ 위상 정렬이란 무기를 이렇게도 활용할 수 있구나.. 싶었다. 다른 문제들도 풀어봐야 할 듯.