[Python] 게임 개발 - 백준 (위상정렬)

해당 글은 백준 1516번 '게임 개발' 문제를 다룬다.

문제

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

1516번: 게임 개발

 

설명

해당 문제는 순서가 정해져있는 일련의 작업을 차례대로 수행할 때 사용하는 위상 정렬 알고리즘으로 해결할 수 있다.

저장할 그래프는 방향이 있으므로 노드 A에서 노드 B로 갈 때의 간선만 저장한다.

또한, 결과값을 담는 result는 time 리스트를 깊은복사하여 사용한다.

 

코드

from collections import deque
import copy

n = int(input())
indegree = [0]*(n+1)
graph = [[] for _ in range(n+1)]
time = [0]*(n+1)

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

result = copy.deepcopy(time)
q = deque()

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

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

for i in range(1, n+1):
    print(result[i])