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

1일 1PS 41일차!

📚 문제

---

골드 3

• 위상 정렬과 DP

💡 풀이 과정

---

1. 위상 정렬을 사용한다.
2. 진입 노드의 수를 저장하고 각 노드의 후수 노드를 리스트로 정렬한다.
3. 위상 정렬 중 현재 노드(A) 에서 다음 노드(B) 로 이동 시 DP[B] 와 DP[A] + cost[B] 중 최대 값을 DP[B] 에 저장한다.

📌포인트

---

• dic[int(n)].append(i)
  • while 문에서 현재 노드를 선수 노드로 가지는 노드들의 진입 노드 수를 -1 해야하기에 후수 노드들을 리스트로 저장한다.

💻 코드

---

from collections import deque

N = int(input())

dic = {}
for i in range(1, N + 1):
    dic[i] = []
indegree = [0] * (N + 1)
cost = [0] * (N + 1)
dp = [0] * (N + 1)

for i in range(1, N + 1):
    temp = input().split()
    dp[i] = cost[i] = int(temp[0])
    indegree[i] = len(temp[1:-1])
    for n in temp[1:-1]:
        dic[int(n)].append(i)

queue = deque()

for i in range(1, N + 1):
    if indegree[i] == 0:
        queue.append(i)

while queue:
    node = queue.popleft()
    for n in dic[node]:
        n = int(n)
        indegree[n] -= 1
        if indegree[n] == 0:
            queue.append(n)
        dp[n] = max(dp[n], cost[n] + dp[node])

for node in dp[1:]:
    print(node)