[Baekjoon] 1516번 : 게임 개발 (Python, 위상 정렬, DP)

[Baekjoon] 1516번 : 게임 개발 (Python, 위상 정렬, DP)

 

목차

 

https://www.acmicpc.net/problem/1516

1516번: 게임 개발

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Python

 

방법 1 - 메모리 32452KB / 시간 136ms / 코드 길이 653B

 

1005번과 마찬가지로 위상정렬과 DP가 결합된 문제이다.

https://aigong.tistory.com/457

[Baekjoon] 1005번 : ACM Craft(Python, 위상 정렬, DP)

 

순서가 존재하는 모든 노드에 대해 순서대로 나열하는 위상 정렬에서 DP를 활용하여 시간을 계산해내는 문제이다. 

다만 본 문제는 입력이 특이한데 이점을 유의하면서 코드를 구성해야 한다.

 

 

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

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

for i in range(1, n+1):
    t = list(map(int, input().split()))
    time.append(t[0])
    for j in t[1:-1]:
        graph[j].append(i)
        indegree[i] += 1


res = [0] * (n + 1)
q = deque()

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

while q:
    now = q.popleft()
    for k in graph[now]:
        indegree[k] -= 1
        res[k] = max(res[now]+time[k], res[k])
        if indegree[k] == 0:
            q.append(k)

for i in res[1:]:
    print(i)