[Python] 백준 1516 게임 개발

1516번: 게임 개발

위상정렬 : 위상정렬 문제를 두번째 푸는 건데 느낌이 비슷한 것 같다. inDegree에 진입차수를 집어넣는게 핵심이다. 진입차수가 0이면 큐에 집어넣고 돌려준다. DP값에는 조건에 맞게 값을 넣어주면 된다.

 

전체코드

import sys
import collections

input = sys.stdin.readline

N = int(input())
times = [0 for _ in range(N + 1)]
dp = [0 for _ in range(N + 1)]
inDegree = [0 for _ in range(N + 1)]
graph = collections.defaultdict(list)
for i in range(1, N + 1):
    tmp = list(map(int, input().split()))
    times[i] = tmp[0]
    tmp = tmp[1:-1]
    for j in tmp:
        graph[j].append(i)
    inDegree[i] = (len(tmp))

queue = collections.deque()
for i in range(1, N + 1):
    if inDegree[i] == 0:
        queue.append(i)
        dp[i] = times[i]

while queue:
    node = queue.popleft()
    for i in graph[node]:
        inDegree[i] -= 1
        dp[i] = max(dp[node] + times[i], dp[i])
        if inDegree[i] == 0:
            queue.append(i)

for i in range(1, N + 1):
    print(dp[i])