Barbera

www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 다음은 위상정렬의 개념을 이해했다고 가정한 풀이설명입니다. 문제의 조건을 토대로 의 건물을 짓기위한 순서를 그래프로 표현하면 다음과 같습니다. 문제의 조건을 보면 모든 입력은 위의 그림처럼 방향성이 있는 비순환 그래프(DAG)로 나타낼 수 있고 건물을 짓기 위한 순서를 필요로 하므로 각각의 건물을 완성하기 위한 최소시간은 위상정렬을 이용해 구할 수 있습니다. 위상정렬로 순서를 구하는 과정에서 n번건물..