[BOJ][1516] 게임 개발

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

---

전형적인 위상정렬 문제.

입력값들로 위상 정렬을 위한 그래프를 먼저 만든다.

건물의 cost 정보를 배열에 따로 저장해둔다.

큐를 하나 만들어서 우선시 개발되어야 하는 건물들이 없는 건물 인덱스를 모두 넣는다.

큐에 들어갈 때 각 건물이 완성되기까지 걸리는 최소 시간이 정해진다.

처음 큐에 값을 세팅할 때는 자기 자신이 만들어지는데 걸리는 시간이 각 건물이 완성되기까지 걸리는 최소 시간이 된다.

큐를 pop하면서 가져온 인덱스 건물(A)과 앞서 만든 그래프에서 간선을 가지고 있는 건물(B)에서 해당 간선 (A -> B)을 제거한다.

간선이 있다는 뜻은 B 건물을 만드는데 A 건물이 우선시되어 만들어져야 한다는 의미이다.

따라서 B 건물을 만드는데 걸리는 최소 시간을 갱신한다. 이때까지 탐색하면서 구한 최소 시간보다 A 건물을 만드는데 걸리는 최소 시간 + B 건물만을 만드는데 드는 시간이 더 적다면 갱신된다.

A -> B 간선을 제거했을 때 더 이상 x -> B 간선에 해당하는 x 건물이 없다면 B를 만들기 위해 우선시 되어야 하는 건물이 모두 만들어졌다는 의미이므로 B건물을 만들 수 있다. 즉, B를 큐에 넣는다.

이를 큐가 빌때까지 탐색한다.

시간 복잡도는 O(NE).

---

소스코드 : https://gist.github.com/fpdjsns/918d6b24606d34f8daa371d98c993078