BaekJoon1516_게임 개발

문제

풀이

위상 정렬에 대해 익숙하지 않아 문제를 푸는데 애를 많이 먹었다. 위상 정렬에 대해 공부를 진행한 뒤 다시 푸니 의외로 쉽게 풀렸다.

풀이 코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

building = [[] for _ in range(n+1)]
indegree = [0] * (n+1)
times = [0] * (n+1)

for i in range(1,n+1):
    temp = list(map(int,input().split()))
    times[i] = temp[0]
    data = temp[1:len(temp)-1]

    for j in data:
        building[j].append(i)
        indegree[i] += 1


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

    while q:
        now = q.popleft()
        
        answer[now] += times[now]

        for b in building[now]:
            indegree[b] -= 1
            
            answer[b] = max(answer[b], answer[now])

            if indegree[b] == 0:
                q.append(b)
    return answer


answer = topology_sort()

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