054 임계경로

첫번째 코드

 

아직 위상정렬 코드가 어색하다.

또한 이를 이용해서 문제를 해결하는 능력이 아직 부족하다...

코드는 책을 참고했다!

코드를 작성하면서 이해가 잘 되었는데...내가 이걸 혼자 쓸 수 있을까 ㅎㅎ;

 

from collections import deque

n = int(input())
A = [[] for _ in range(n+1)]
indegree = [0] * (n+1)
answer = [0] * (n+1)

for i in range(1, n+1):
    input_list = list(map(int, input().split()))
    answer[i] = (input_list[0])
    index =1

    while True:
        preTemp = input_list[index]
        index += 1
        if preTemp == -1:
            break
        A[preTemp].append(i)
        indegree[i] += 1

queue = deque()

for i in range(1, n+1):
    if indegree[i] == 0:
        queue.append(i)

result = [0] * (n+1)

while queue:
    now = queue.popleft()
    for next in A[now]:
        indegree[next] -= 1
        result[next] = max(result[next], result[now] + answer[now])
        if indegree[next] == 0:
            queue.append(next)

for i in range(1, n+1):
    print(result[i] + answer[i])

 

통과!

위상정렬 코드와 익숙해지는 중!!!

다음에 혼자 풀어보도록 하자!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1516.%E2%80%85%EA%B2%8C%EC%9E%84%E2%80%85%EA%B0%9C%EB%B0%9C

programmers/백준/Gold/1516. 게임 개발 at main · ornni/programmers