위상 정렬

위상 정렬..?

순서에 조건이 붙어있는 경우 일반적인 DFS같은 것으로 구현했을 때, 깔끔하게 구현이 되지 않음을 많이 느꼈다. 이때마다 위상 정렬이라는 개념이 등장했고, 위상 정렬에 대해서 제대로 정리해보자

위상 정렬 : 주어진 조건을 위배하지 않으면서, 노드를 순서대로 정렬하는 것

위상 정렬의 조건

위상 정렬을 할 그래프는 DAG이어야 한다.
DAG : Directed Acyclic Graph, 직접 연결된 사이클이 없는 그래프
한 마디로 사이클이 있는 그래프에서는 위상 정렬을 할 수가 없다
why? => 사이클이 존재하게 되면, 선행 조건이 없는 노드(시작점)을 찾을 수가 없기 때문에!!

위상 정렬 하는법

1. 진입차수가 0인 node를 큐에 삽입
   • 진입차수 : node에 들어오는 edge의 수(한마디로 선행 조건의 수)
2. 큐에서 원소를 꺼내 해당 노드와 연결된 edge를 제거
3. edge 제거 후 진입 차수가 0인 node를 큐에 삽입
4. 만약 모든 원소를 방문하기 전에 큐가 비면, 사이클이 존재한다!
5. 그렇지 않다면, 큐에서 꺼낸 순서가 위상 정렬의 순서!

4번 과정을 보면, 그래프에 사이클이 존재하는지를 파악하는 방법도 위상 정렬이다.

위상 정렬에 대해 알아봤는데 생각보다 어렵지 않았다. 개념을 적용해서 문제를 풀어보자.

백준_1766번

• 문제를 조건에 맞는 순서대로 풀어야 한다
• 조건 중에 가능한한 쉬운 문제부터 푼다는 조건때문에 heap이 필요하다!
• 진입차수를 저장할 배열과 그래프 경로를 저장할 공간이 필요하다
• 이를 활용하여 위에 적혀진 방법대로 구현하면 어렵지 않다
• 링크 : https://github.com/htogether7/algorithm/blob/main/graph/1766.py