[자료구조/알고리즘] 위상 정렬(Topology sort)

위상 정렬은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미하는데, 대학의 선수과목 구조가 대표적인 예이다. 정렬의 순서는 여러 가지가 나올 수 있으며, 비순환 그래프일 때만 정렬이 가능하다.

비순환 유향 그래프가 주어진 상황에서의 위상 정렬의 예시, 출처: 위키백과

위상 정렬 알고리즘의 동작 원리 및 순서는 아래와 같다. 선행되는 노드가 없는 노드들을 먼저 순서에 삽입하는 것을 기본 원리로 한다.

 

① 자기 자신을 가리키는 간선의 수를 진입 차수라 할 때, 진입 차수가 0인 모든 노드를 큐에 삽입한다.

② 큐에서 원소 하나를 꺼내어, 순서 배열에 이를 삽입하고 해당 노드가 가진 모든 간선을 삭제한다. 여기서 삭제한다는 것은 해당 간선으로 발생된 진입 차수를 없애는(-1) 것을 말한다. 이때 진입 차수가 줄어드는 노드의 진입 차수가 0이 된다면, 이 노드를 큐에 삽입한다.

③ 큐에 원소가 있는 동안 ②의 과정을 반복한다.

④ 순서 배열의 길이가 전체 노드의 수보다 작은 상태에서 반복문이 종료된다면, 이는 사이클이 존재한다는 의미이므로 위상 정렬이 불가능한 경우에 해당한다.

 

문제 및 코드 예시: https://mingchin.tistory.com/347

[코딩 테스트 연습(파이썬/Python)] 백준 2623번 _ 음악프로그램