백준 2637번 python 풀이 - 장난감 조립

문제 링크

2637번

해결책

import sys

N = int(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())

indegree = [0 for _ in range(N + 1)]

path = [[] for _ in range(N + 1)]

for _ in range(M):
    _to, _from, val = map(int, sys.stdin.readline().rstrip().split())
    path[_from].append((_to, val))
    indegree[_to] += 1
    path[_from].sort(key=lambda x: x[0])

que = []
base = []

for _ in range(1, N + 1):
    if indegree[_] == 0:
        que.append(_)
        base.append(_)



needs = [[0 for i in range(N + 1)] for j in range(N + 1)]

while que:
    cur_v = que.pop(0)
    for nxt_v, nxt_w in path[cur_v]:
        if (cur_v in base):
            needs[nxt_v][cur_v] += nxt_w
        else:
            for i in range(1, N + 1):
                needs[nxt_v][i] += needs[cur_v][i] * nxt_w
        indegree[nxt_v] -= 1
        if indegree[nxt_v] == 0:
            que.append(nxt_v)

for i in base:
    print(i, needs[-1][i])

주석으로 달 설명

으악 위상정렬 2번… 위상 정렬 자체는 어렵지 않은데, 뭔가 이런식으로 꼬이기 시작하면 밑도끝도없이 내려간다… 여기에서의 포인트는, indegree가 0인 놈들을 넣는것 뿐만 아니라, 조금의 DP와 함께 기존값을 저장하여, 이 저장된 것들을 집어넣어주는것이 포인트였다.