[BOJ] 백준 1005 ACM Craft

문제 링크

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번을 동시에 지을 수 있다.

1번 건물이 10초 만에 지어졌으므로 2번 건물은 $10 + 1 = 11$초, 3번 건물은 $10 + 100 = 110$초 만에 지어진다.

$n$	1	2	3	4
$d$	10	11	110	0

$step\,3)$

2번 건물이 11초 만에 완성됐지만, 아직 3번 건물이 완성되지 않았으므로 4번 건물은 3번이 다 지어진 후에 지을 수 있다. 따라서 $110 + 10 = 120$초 만에 지어진다.

$n$	1	2	3	4
$d$	10	11	110	120

여기서 우리는 어떤 건물 $n$의 완성 시간을 구하기 위해 직전 단계에 필요한 건물들이 필요로 하는 총 시간 중, 가장 오래 걸리는 시간을 택해 $n$을 짓는데 걸리는 시간을 더해야 하는 것을 알 수 있다.

정답 코드