이번에는 위상 정렬에 대해 정리하고, 문제를 기준으로 이해해보자!

위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.

4 2
4 2
3 1

위상 정렬, Topology Sort?

위상 정렬은 뱡향이 정해져 있는 그래프에서 순서대로 정렬하기 위해 사용되는 알고리즘이다.

특히 이 알고리즘은 **방향이 있으며 순환하지 않는 그래프, DAG(Directed Acyclic Graph)**에만 적용이 가능하다는 조건이 붙는다.

위상 정렬을 구현하기 전에 이해해야 할 두 가지 개념을 이해해두면 도움이 될 것이다.

진입차수 (in-degree, 입력차수)

• 어떤 노드 N으로 향하는 간선의 개수

진출차수 (out-degree, 출력차수)

• 어떤 노드 N에서 다른 노드로 향하는 간선의 개수

위 문제의 입력이 들어왔을 때, 아래와 같이 유향 그래프가 만들어지는데, 이 때의 진입차수와 진출차수를 구해보면 아래와 같다.

위상 정렬에서는 ****보통 진입차수와 큐를 이용한 구현을 많이 이용한다.