[알고리즘] 위상 정렬 (Topology Sort)

개념 여러 작업이 있을 때 특정 작업을 수행하기 전 진행되어야 할 작업들이 있다. 이 작업들을 순서에 맞게 정렬해주는 것이 위상정렬이다.

위상정렬의 그래프는 의존성 그래프 (Dependency Graph) 의 모양을 띄고 있어야 하는데, 그 말은 각 정점(작업)의 의존 관계를 간선으로 나타낸 방향 그래프라는 의미이다. 만일 작업 v는 u가 끝나야만 수행할 수 있다면, 그래프는 u->v로 향하는 간선을 포함하게 된다.

이러한 의존성 그래프에서는 사이클이 존재할 수 없다. 구현방식 (1) indegree 순서가 정해져 있는 요소 조건에 따라 그래프를 그려보고 각 노드들에 대한 진입 차수(inDegree)를 구하고 이것이 0인 지점부터 차례대로 탐색 1.

자..........