[알고리즘] 위상 정렬

[백준/Kotlin] 줄 세우기(2252)

 

위에서 풀이한 백준 문제를 풀 때 위상 정렬이라는 개념을 사용했는데, 어려워서 솔루션을 찾아 해결했었다. 위상 정렬에 대해 이해하고자 정리 해두려 한다!

 

✅ 위상 정렬이란?

• 사이클이 없는 방향 그래프를 정렬한다고 생각하면 된다.
• 방향 그래프를 방향성에 거스르지 않게 순서대로 나열하는 것

---

위상 정렬 알고리즘을 이해하려면 진입차수, 진출차수를 알아야 한다.

• 진입차수: 노드로 들어오는 간선의 개수
• 진출차수: 노드에서 나가는 간선의 개수

예를 들어, A -> B라면 A의 진입차수가 0이고, 진출차수가 1이다. 반대로 B의 진입차수는 1이고 진출차수는 0이다.

A -> B 라는 표시를 A가 B보다 앞에 있어야 하는데, 이때 진입차수가 0이면 해당 노드보다 앞에 위치해야 하는 노드가 없다는 뜻이 된다.

 

따라서 다음 과정을 거치면 정렬을 할 수 있게 된다.

1. 각 노드의 진입차수를 구한다.
2. 진입차수가 0인 노드를 큐에 넣는다.
3. 큐에서 원소를 꺼내 나열하고, 해당 노드에서 나가는 간선을 그래프에서 제거한다. (해당 노드가 진입하는 노드의 진입차수를 -1 해준다)
4. 3번 이후 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
5. 큐가 빌 때까지 3, 4번을 반복한다.

 

+) 참고

[알고리즘] 위상 정렬 (Topological Sorting)

 

위상 정렬(Topological sort) 개념 및 구현