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

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

아이디어

• 이전 일이 끝나야지만 다음 일을 할 수 있는 순서가 정해져있는 작업을 다루는 문제 -> 위상정렬을 사용하자
• 아래 리스틀를 선언해두고 사용하자
• 그래프
• 진입 차수(사전에 진행되어야 하는 건물 개수)
• 건물별 걸리는 시간 저장
• DP (사전 진행되어야 하는 건물 중 가장 늦게 건설되는 건물을 기준으로 코스트 계산)

구현

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

# 순서ㅇ가 있는 작업 -> 위상 정렬을 사용하자
# 그래프 배열, 진입 차수 배열, 비용 배열, DP 배열 
N = int(input())
graph = [[] for i in range(N)]
indegree = [0] * N
cost = [0] * N
DP = [0] * N


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

q = deque()

for i in range(N):
    if indegree[i] == 0:
        DP[i] = cost[i]
        q.append(i)

while q:
    n = q.popleft()
    
    for i in graph[n]:
        indegree[i] -= 1
        # 선행 건물 중 가장 오래 걸리는 시간 + 나의 건축 시간을 찾아야함
        DP[i] = max(DP[i], DP[n] + cost[i])
        
        if indegree[i] == 0:
        	q.append(i)

for i in range(N):
    print(DP[i])

 

마무리

생각이 위상정렬까지는 났지만 DP까지 연계되진 않았다. DP 점화식을 이해하는게 좀 어려웠지만 못할 정도는 아니였떤거 같다.

그냥 문제에 어떤 알고리즘을 적용시켜야 할진만 떠올랐다면 쉽게 풀렸을 문제였다. 난 아직 연습이 더 필요해 보인다..