데구리 블로그

문제 링크 https://www.acmicpc.net/problem/1005 "모든 건물을 지을 수 없는 경우는 없다."라는 조건에서 주어진 그래프가 싸이클 없는 방향 그래프(DAG)라는 걸 알 수 있다. 건물을 짓는 순서가 정해져 있으므로 위상정렬로 해결할 수 있다. 단순 BFS로는 풀기 힘들다. 본문의 예제를 단계별로 살펴보자. $x$번 건물이 완성될 때까지의 총 시간을 $d[x]$으로 표현하겠다. 아직 완성 시간을 알 수 없는 건물은 0의 값을 가진다. $step\,0)$ 초기상태이다. $n$ 1 2 3 4 $d$ 0 0 0 0 $step\,1)$ 우선 1번 건물을 먼저 지을 수 있고, 10초가 걸린다. $n$ 1 2 3 4 $d$ 10 0 0 0 $step\,2)$ 2번과 3번을 동시에 지을 수 ..