[알고리즘][Python] 백준 1516 게임 개발 문제 풀이

문제 출처 : www.acmicpc.net/problem/1516

1516번: 게임 개발

---

문제 해석 : 각 건물을 건설하기 위해서는 선행되어야 하는 건물이 있다. 이를 고려하였을 때 각 건물이 지어지는데 필요한 최소 시간을 출력하라

 

문제 풀이 :  위상정렬과 DP를 활용하면 풀 수 있다.

---

풀이 코드

from collections import defaultdict, deque

N = int(input())
answer = [0] * (N+1)
cost = [0] * (N+1)
degree = [0] * (N+1)
Q = deque()

graph = defaultdict(list)
for i in range(1,N+1):
    temp = list(map(int, input().split()))
    cost[i] = temp[0]

    for element in temp[1:-1]:
        graph[element].append(i)
        degree[i] += 1


for i in range(1,N+1):
    if degree[i] == 0:
        Q.append(i)
        answer[i] = cost[i]

while Q:
    now = Q.popleft()
    for element in graph[now]:
        degree[element] -= 1
        answer[element] = max(answer[element], cost[element] + answer[now])

        if degree[element] == 0:
            Q.append(element)


for i in range(1, len(answer)):
    print(answer[i])

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.