게임 개발[백준 1516] - python

import heapq
import sys
input = sys.stdin.readline

def BOJ1516() :
  N = int(input())
  time = [0 for _ in range(N+1)]
  graph = [[] for _ in range(N+1)]
  indegree = [0 for _ in range(N+1)]
  queue = []
  result = [0 for _ in range(N+1)]

  for i in range(1, N + 1) :
    temp = list(map(int, input().split()))
    time[i] = temp[0]
    temp_graph = temp[1:-1]
    indegree[i] = len(temp_graph)
    for k in temp_graph :
      graph[k].append(i)
  
  for i in range(1, N+1) :
    if indegree[i] == 0 :
      heapq.heappush(queue, (time[i], [i, time[i]]))

  while queue :
    _, [curr, curr_time] = heapq.heappop(queue)
    result[curr] = curr_time
    for i in graph[curr] :
      indegree[i] -= 1
      if indegree[i] == 0 :
        next_time = curr_time + time[i]
        heapq.heappush(queue, (next_time, [i, next_time]))

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

BOJ1516()

접근방법 :

1. 입력이 되게 까다로웠던 문제인걸로 기억한다.

2.다른 건물을 선행해서 지어야 하는 조건이 있으므로 위상정렬을 적용했고 동시에 여러개의 건물을 지을수 있다는 점과 최소시간을 출력해야 한다는 점으로 말미암아 우선순위 큐를 적용하였다. 

이전 포스팅에서 우선순위 큐를 적용하는 이유를 참고할 수 있다.

 

 

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

1516번: 게임 개발