[BOJ] Q1516 게임 개발

[BOJ] Q1516 게임 개발

Question

Language: Python

Difficulty: Gold 3

해당 문제는 각 건물에 대해 건물을 지을 수 있는 시간을 구하는 문제로, 각 건물에 대해 먼저 지어져야하는 건물이 있는 경우 해당 건물이 지어져야 현재 건물을 지을 수 있다. 이 처럼, 각 건물에 대해 선입 조건이 있는 경우를 고려해야하며 이러한 유형의 문제는 Topological Sorting을 통해 건물 순서에 대한 정렬을 수행한다.

Solution

from collections import deque
from math import inf

def solution():
    distances=[0]*n
    graph=[[] for _ in range(n)]
    processing_time=[0]*n
    indegrees=[0]*(n)
    
    #간선을 연결해주는 작업 --> 각각의 간선은 건물 간에 우선순위를 의미한다. a->b인 경우 b를 짓기 위해 a가 지어져야함을 의미한다.
    for vertex in range(n):
        processing_time[vertex]=edges[vertex][0]

        for adj_vertex in edges[vertex][1:]:
            if adj_vertex ==-1:
                break
            graph[adj_vertex-1].append(vertex)
        
            indegrees[vertex]+=1

    queue=deque()
    #들어오는 간선이 없는 노드들을 큐에 삽입한다.
    for vertex in range(n):
        if indegrees[vertex]==0:
            queue.append(vertex)
            distances[vertex]=processing_time[vertex]
    
    #topological sorting을 진행하면서 각 노드에 도달할 수 있는 가장 마지막 시간대를 구하는 것을 통해 모든 선제 조건들이 만족되도록 한다.
    while queue:
        vertex=queue.popleft()
        for adj_vertex in graph[vertex]:
            distances[adj_vertex]=max(distances[adj_vertex],distances[vertex]+processing_time[adj_vertex])
            indegrees[adj_vertex]-=1

            if indegrees[adj_vertex]==0:
                queue.append(adj_vertex)
        
    
    for distance in distances:
        print(distance)

if __name__ == "__main__":
    n=int(input())
    edges=[list(map(int,input().split())) for _ in range(n)]

    solution()