백준 1516 위상정렬

[baekjoon 1516] 게임 개발 (위상정렬, DP) (C++)

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 입력으로 각 건물을 짓는데 걸리는 시간과, 이 건물을 짓기 위해서 선행되어야 하는 건물의 번호가 주어진다. 즉, 건물을 짓는 순서를 그래프로 나타내면 DAG(Directed Acyclic Graph) - 사이클을 갖지 않는 단방향 그래프가 되고, 이를 통해 노드 간 고유 순서를 위배하지 않으면서 정렬하는 위상 정렬을 이용할 수 있다. 위상 정렬의 방법은 1. 스택을 이용하는 방법과 2...