위상정렬. [2056]

[1. 문제 설명]

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

---

[2. 풀이 접근]

일반적인 위상 정렬 풀이로 접근한다.

• 동시에 처리가능한 작업들이 있으므로, bfs 를 응용하여 처리한다.
• dfs 로는 "동시에 처리 가능한 작업" 에 대한 처리가 힘들다.

주의 할 점

• 전체 작업이 끝나는데 걸리는 시간은 가장 마지막에 실행되는 작업에 의존적이지 않다.
• 가장 마지막에 끝나는 작업에 의존한다.
• 예를들어,  {a -> b}, {d -> e -> f} 가 있을 때,
• f 가 가장 마지막에 실행 되지만,  b 를 처리하는데 걸리는 시간이 다른 작업 보다 월등히 크다면
• 이러한 접근은 후순위 작업의 실행 시점에도 영향을 준다.
• => 코드 참조.

---

[3. 코드]