위상정렬. [1516]

[1. 문제 설명]

https://www.acmicpc.net/problem/1516

---

[2. 풀이 접근]

문제에서 다음과 같은 조건이 있다.

1. 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다.
2. 여러 개의 건물을 동시에 지을 수 있다.
3. N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다.

1번 조건을 통해 일정한 순서를 지켜야 한다는 것을 알 수 있다.

여기에서 위상 정렬을 통해 접근 해볼 수 있음을 알 수 있다.

 

 

2번 조건은 조금 까다로울 수 있지만, 3번 조건을 통해 풀이의 힌트를 얻을 수 있다.

전체 건물대신, A 라는 어떤 하나의 건물에만 초점을 맞춰보자.

A 라는 건물을 짓기 위해서는 A`, B`, C` 라는 건물을 먼저 지어야 하고,

A`, B`, C` 의 건물을 짓기 위해 먼저 지어야 하는 건물이 없다고 가정해보면,

 

A 라는 건물은 A`, B`, C` 이 세개의 건물을 짓기 시작하고,

가장 마지막에 지어지는 건물 다음에 짓기 시작한다.

 

이러한 방식을 전체 건물에 대해서 적용하면,

동시에 지어야 하는 것에 초점을 맞출 필요 없이

먼저 지어야하는 건물로 초점을 맞추는 것이 더 중요하다는 것을 알 수 있다.

 

 

만약 문제에서 요구하는 바가 전체 건물이 지어지는데 걸리는 시간으로 한다면,

이 문제와 동일한 풀이를 한 뒤,

전체 건물 중 가장 마지막에 완성 된 건물을 짓는데 걸린 시간을 출력하면 된다.

• 동시에라는 조건이 살짝 까다로울 수 있지만,
• 개별에 대해서 생각해도 되며,
• ...

 

## 처음 풀이 시 실수한 사항

1. 단순한 위상정렬로 접근
2. 아래와 같은 상황에서 오답을 출력
3. 4번 건물의 부모가 3번만 있다고 생각했기 때문.
4. 4번 건물은 3번과 5번이 지어진 후 지을 수 있지만,
   BFS 순서 상 3번이 지어진 후 4번을 지을 수 있어서
   4번 건물의 부모가 3번만 저장되었고,
   3번 건물을 짓는 시간이 60 이므로 4번 건물이 100 만에 지어진다고 계산했음
5. 그러나 5번 건물은 제일 처음에 시작하지만 3번 건물보다 늦게 지어짐
6. 따라서 4번은 가장 마지막에 건설되는 5번 다음에 짓는게 맞다.

---

[3. 코드]