[Baekjoon 1516] 게임 개발

문제

💛Ⅲ [Baekjoon 1516 - 게임 개발]

문제 풀이 방법

순서가 정해져 있는 일련의 작업을 순서대로 수행해야 하기 때문에 위상 정렬 알고리즘을 이용하여 풀이할 수 있다. 하지만 각 노드에 비용이 있기 때문에 조금 더 까다로웠다.

처음에는 indegree가 0이 될 때만 비용을 계산해주었는데, 특정 노드가 여러 번 갱신될 수 있는데 이때 전에 계산된 비용보다 작은 값이 존재할 수 있다는 반례가 있었다. 그래서 진입차수를 줄일 때마다 비용을 계산하고, 현재 노드의 비용과 비교하여 더 큰 값을 저장하여 해결하였다.

1. 각 건물의 비용을 저장하는 cost와 진입차수를 저장하는 indegree를 초기화한다.
2. 진입차수가 0인 노드를 큐에 넣고, 비용을 answer 배열에 더해준다.
3. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거하고, 현재 answer에 저장된 비용과 현재 노드를 거쳐서 발생하는 비용 중 더 큰 값을 대입한다.
   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

주의할 테스트 케이스‼️

입력 > 
5
10 -1
20 1 -1
30 2 -1
40 3 5 -1
100 -1
==========
정답 > 
10 
30 
60 
140 
100
==========
틀린 결과 > 
10 
30 
60 
100 
100

풀이 코드

Python

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

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

def topology_sort():
    q = deque()

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

    while q:
        now = q.popleft()
        for i in graph[now]:
            indegree[i] -= 1
            answer[i] = max(answer[i], answer[now] + cost[i])
            if indegree[i] == 0:
                q.append(i)

topology_sort()
for x in answer[1:]:
    print(x)