[Python] 백준 1516번 : 게임 개발

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

1516번: 게임 개발

---

💡 문제 풀이

위상 정렬 문제이다.

 

다른 위상 정렬과 다르게 DP와 같이 들어가 있는 문제이다.

주의해야 할 점은 어떤 건물을 건설할 때 요구하는 건물들이 다 완공되어야 한다.

즉, (가장 마지막에 건설한 건물의 시간) + (어떤 건물 건설 시간)이 더해진 값이 총 건설 시간이다.

✔️ 느낀 점

위상 정렬에 익숙해지고 있는데 이런 복합적인 문제가 나와서 너무 좋았다. 그리고 역시 DP는 나랑 안 맞는다.

이해하느라 너무 힘들었다.

💻 코드

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

N = int(input())
graph = [[] for _ in range(N+1)]
indegree = [0] * (N+1)
cost = [0] * (N+1)
DP = [0] * (N+1)

for i in range(1, N+1):
    tmp = list(map(int, input().split()))[:-1]
    cost[i] = tmp[0]
    for j in tmp[1:]:
        graph[j].append(i)
        indegree[i] += 1
        
q = deque()

for i in range(1, N+1):
    if not indegree[i]: 
        q.append(i)
        DP[i] = cost[i]

while q:
    n = q.popleft()
    
    for i in graph[n]:
        indegree[i] -= 1
        DP[i] = max(DP[i], DP[n] + cost[i])
        
        if not indegree[i]: q.append(i)

for i in range(1, N+1):
    print(DP[i], end='\n')