알고리즘 - 위상 정렬(Topology Sort)
📌 위상 정렬이란?
- 순서가 정해진 작업을 차례대로 수행해야 할 때 사용하며, 사이클이 존재하지 않는 방향 그래프의 모든 노드를 방향을 거스르지 않도록 나열하는 것을 말합니다.
🔍 위상 정렬의 과정
위와 같은 싸이클이 없는 방향 그래프를 위상 정렬해 보겠습니다. 아래는 그 과정입니다.
- 진입 차수가 0인 노드를 큐에 넣는다.
- 큐가 empty가 될 때까지 다음 두 과정을 반복한다.
- 큐에서 원소를 꺼내고, 그 노드에서 출발하는 간선을 제거한다.
- 간선을 제거하면 새롭게 진입 차수가 0이 되는 노드가 있을 것인데, 그들을 큐에 넣는다.
위상 정렬 결과는 큐에서 원소를 꺼낼 때, 그 빠져 나온 순서가 곧 정렬 순서가 됩니다.
진입 차수란? : 특정 노드로 들어오는 간선의 개수를 말합니다.
[1] 진입차수가 0인 1번 노드를 큐에 넣습니다.
[2] 큐에 있는 1번 노드를 꺼냅니다. 그리고 1번 노드와 연결되어 있던 간선을 제거하면, 2번 노드와 5번 노드의 진입 차수가 0이 됩니다. 그러므로 이 노드들을 큐에 넣습니다.
[3] 큐에 있는 2번 노드를 꺼냅니다. 그리고 2번 노드와 연결되어 있던 간선을 제거하면, 3번 노드가 새롭게 진입 차수가 0이 됩니다.
그러므로 3번 노드를 큐에 넣습니다.
[4] 큐에 있는 5번 노드를 꺼냅니다. 그리고 5번 노드와 연결되어 있던 간선을 제거하면, 6번 노드가 새롭게 진입 차수 0이 됩니다. 따라서 큐에 6번 노드를 넣습니다.
[5] 큐에 있는 3번 노드를 꺼냅니다. 그리고 3번 노드와 연결되어 있던 간선을 제거했으나 새롭게 진입 차수가 0이 되는 노드가 없으므로 큐에 넣지 않고 넘어갑니다.
[6] 큐에 있는 6번 노드를 꺼냅니다. 그리고 6번 노드와 연결되어 있던 간선을 제거하면, 4번 노드가 새롭게 진입 차수 0이 됩니다. 따라서 4번 노드를 큐에 넣습니다.
[7] 큐에 있는 4번 노드를 꺼냅니다. 그리고 4번 노드와 연결되어 있던 간선을 제거하면, 7번 노드가 새롭게 진입 차수 0이 됩니다. 따라서 7번 노드를 큐에 넣습니다.
[8] 큐에 있는 7번 노드를 꺼냅니다. 그리고 7번 노드와 연결되어 있는 간선을 제거해야 하는데 제거할 간선이 없고, 따라서 새롭게 진입 차수 0이 되는 노드가 없으므로 큐에 넣지 않고 넘어갑니다.
즉, 위상 정렬의 결과는 1-2-5-3-6-4-7 이 됩니다. 방향성을 거스르지 않고 나열하게 되었습니다.
예를 들어, 그래프에서 보면 1 다음에 2(1->2) , 1 다음에 5(1->5) 라는 방향성이 있으므로 1 다음에 바로 6이 오는 1->6 이라는 나열은 허용되지 않습니다. 이러한 조건을 만족하면서 나열하는 것입니다.
📁 위상 정렬을 활용한 문제
- 준비중
이 포스팅은 이것이 코딩 테스트다(나동빈님 저)를 공부하고 일부 정리한 것입니다.