위상정렬 (Topological Sort) 알고리즘

위상정렬

---

해당 내용을 이해하기 위해선 DFS(링크)에 대한 이해가 필요하다.

 

위상정렬(Topological Sort)는 DFS를 사용하는 대표적인 알고리즘이다.

DFS말고 indegree의 개수를 측정하는 방법도 있다.

알고리즘의 목표는 일의 순서를 정하는 것이다.

 

예를 들어 W1, W2, W3 (W는 할 일이다)이 있다고 가정하자.

W2는 W1을 끝내야만 할 수 있고, W3은 W2를 끝내야만 할 수 있다.

그렇다면 일의 순서는 W1 → W2 → W3로 하면 될 것이다.

예시는 3개밖에 없어서 간단한 암산으로 금방 해결할 수 있지만, 주어진 정보가 많아진다면 골치가 아파진다.

 

이때 사용하는 알고리즘이 바로 위상정렬이다.

다음과 같은 그래프가 있다. 각 노드는 위에서 언급한 '일'이라고 생각한다.

모든 노드에 해당하는 일을 하기 위한 순서를 알고 싶다. 그렇다면 한 노드를 정해서 끝까지 쭉가고, 다시 돌아오고...

뭐가 생각나지 않는가? 바로 DFS이다.

위의 그래프를 DFS를 통해 방문이 완료되는 순서를 적어보면 다음과 같다. (빨간 숫자가 일이 끝난 순서이다)

 

그렇다면 그냥 일이 끝난 순서의 내림차순대로 일을 나열하면 된다. 생각해보면 간단하다. 해당 일이 완료되기 위해선 그 직전의 노드를 방문해야 하는데, 이를 역순으로 나열하면 당연히 일의 순서가 된다.

따라서, 1 → 6 → 2 → 3 → 4 → 5 이라는 해답을 얻을 수 있다.

 

위상정렬을 이용하는 문제는 백준 2252 (줄세우기)이다.

그냥 DFS를 하고 끝난 순서대로 stack에 집어넣어서 다시 꺼내기만 하면되는데 무려 골드2티어이다!

우리는 또하나의 고급 알고리즘을 쉽게 배웠다.