위상정렬 Topology Sort (위상 정렬 백준 문제)

 위상 정렬(Topology Sort)은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용한다. -> 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열한다. 이 말을 책에서 보고 이해가 되지 않았다. 예시를 보면 바로 이해할 수 있다.

 

 라면을 끓여 보자. 이 과정을 먹기, 물 끓이기, 스프 넣기, 면 넣기로 나누어 보겠다. 우선 물을 끓여야 면을 넣든 수프를 넣든 하고 그 과정이 일어나야 먹을 수 있다. 이렇게 작업들을 먼저 일어나야 하는 일을 차례대로 정렬해야 한다. 

 

 위상 정렬을 보기전에 진입차수라는 개념을 알아야 한다. 진입 차수는 한 노드로 들어오는 간선의 개수이다. 즉 본인을 향하고 있는 화살표의 수를 의미한다. 아래 그림에서 면 넣기의 진입 차수는 2이다.

위상 정렬 전 라면 끓이기

 위의 그래프를 정의에서 말한 것처럼 일련의 작업을 차례대로 수행해보자 -> 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열해보자.

위상 정렬 예시 1

 

---

위상 정렬 예시 2

 

 그림을 보면 알 수 있듯이 위상 정렬은 여러 개의 결과를 가질 수 있다. 책에서 나온 예제는 선수과목 학습이었다. A라는 과목을 들어야 B라는 과목을 들을 수 있고 이런 예시가 나왔다.

 

 

 위상 정렬의 알고리즘은 다음과 같다.

 

 1. 진입차수가 0인 노드들을 큐에 넣는다.

 2. 큐에서 노드를 꺼내서 해당 노드가 가리키는 즉 이 노드에서 출발하는 간선을 제거한다.

 3. 다시 진입차수가 0인 노드를 찾아 큐에 넣는다.

 4. 2~3 단계를 큐가 빌 때까지 반복한다. 

 

 어렵지 않다. 노드에 큐를 넣을 때 해당 노드를 순서대로 따로 저장하면 위상 정렬 결과가 나온다. 진입 차수가 0이라는 노드가 여러 개 일 경우 시작하는 노드를 정하는 방식에 따라 위상 정렬 결과가 여러 개 나올 수 있다. (위의 라면 예시에서도 처음 물 끓이기 노드에서 시작하는 간선을 지운 후 스프 넣기, 면 넣기 노드의 진입 차수가 0 이여서 선택 순서에 따라 결과가 2개 나왔다.)

 

아래 문제도 순서의 조건이 정해져 있어 위상 정렬로 해결하는 문제이다.

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기