BOJ-1516 - Python

n개의 건물을 짓는다. 이 때 어떤 건물은 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다. 이 때 각 건물마다 짓는데 걸리는 최소시간을 출력하는 문제. deque를 사용한 위상정렬 방법을 이용해 풀었다. 진입차수를 줄이는 과정해서 현재 선수 건물과 현재 건물의 값을 더한 것과 저번 선수 건물과 더한 값 혹은 자신의 값을 비교해 큰 것을 할당하는 점화식 answer[next] = max(answer[next], answer[now] + times[next])을 사용하여 풀었다

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

n = int(input())
tree = [[] for _ in range(n+1)]
times = [0 for _ in range(n+1)]
answer = [0 for _ in range(n+1)]
inDegree = [0 for _ in range(n+1)]

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

    if inputs[1] == -1:
        continue
    for before in inputs[1:]:
        if before == -1: break
        tree[before].append(i)
        inDegree[i] += 1

q = deque()
for i in range(1, n+1):
    if inDegree[i] == 0:
        q.append(i)

while q:
    now = q.popleft()
    for next in tree[now]:
        inDegree[next] -= 1
        answer[next] = max(answer[next], answer[now] + times[next])
        if inDegree[next] == 0:
            q.append(next)

[print(ans) for ans in answer[1:]]

Written by@hyesungoh
Learning every moment

InstagramGitHubLinkedIn