파이썬 백준 1516 게임 개발

import sys
input = sys.stdin.readline
from collections import deque
 
Vn = int(input())
V = {}
for i in range(1, Vn + 1) : 
    V[i] = []
B = [0 for i in range(Vn + 1)]
parent = [0 for i in range(Vn + 1)]
for i in range(1, Vn + 1) : 
    l = list(map(int, input().split()))
    B[i] = l[0]
    for j in range(1, len(l) - 1) : 
        V[l[j]].append(i)
    parent[i] = parent[i] + len(l) - 2
 
que = deque()
for i in range(1, Vn + 1) : 
    if parent[i] == 0 : 
        que.append(i)
 
D = B[:]
while que : 
    now = que.popleft()
    for next in V[now] : 
        D[next] = max(D[next], D[now] + B[next])
        parent[next] = parent[next] - 1
        if parent[next] == 0 : 
            que.append(next)
for i in range(1, Vn + 1) : 
    print(D[i])
 
 

1005 ACM Craft의 코드(https://uneducatedjungler.tistory.com/88)와 구조는 같다.

이전엔 DFS로 풀었으니 BFS로 구현해보았다.