Tag: topological sort

탐색 완료: 1, 2, 3

이렇게 목표 건물이 4번이 queue에 들어와 탐색을 마치면 4번 건물을 지었다는 것이므로 탐색을 멈추고 저장해두었던 시간을 출력하면 된다.

이 문제의 입력으로 주어지는 건물들로 만들어진 그래프는 항상 방향성을 가지며, 항상 모든 건물이 건축 가능하도록 주어진다고 했기 때문에 acyclic이다. 즉 이 문제의 그래프는 DAG(Directed Acyclic Graph)이다. DAG에서 어떤 노드로 들어오는 간선의 개수를 indegree라고 하는데 이 indegree의 개수에 따라 정렬하는 것을 위상 정렬(topologicla sort)이라고 한다.

따라서 우리가 위에서 필요 건물(indegree)에 따라 정렬하여 시간을 계산한 것은 위상 정렬을 이용한 알고리즘인 것이다.