알고리즘 & 자료구조/Topology(위상정렬)
[백준] 게임 개발_1516
문제 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 개요 문제를 먼저 읽어보면 눈에 띄는 문장은 최소 시간을 계산해야 한다는 것이고 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다는 것이다. 이는 Topology(위상정렬)의 전형적인 문제 스타일이다. 위상정렬 알고리즘을 요약하자면 그래프의 Indegree가 0인 노드를 그래프에서 제외시키는 과정을 반복적으로 수행하면서 결국에는 그래프 전체 노드를 지우게 되는 방식으로 문제를 해결하는 알고리즘이다. 이 때 그래프는 사이클(Cycle..