위상 정렬(Topological Sort)

---

목록

- 위상 정렬(Topological Sort) 이란?

- 위상 정렬을 그림을 통해 알아보기

- 위상 정렬 구현 과정(BFS 기준)

- 위상 정렬 구현 :: BFS

---

위상 정렬(Topological Sort) 이란?

남자들이라면 다들 아는 스타크래프트에서 펙토리를 짓기 위해서는 

커맨드 센터 -> 배럭스 -> 펙토리를 올려야 하는 것을 알 것이다.

여자들이라면 화장을 하기위해 

토너 -> 스킨 -> 에센스 -> 수분크림 -> 자외선 차단제 -> 베이스 -> 파운데이션 순서로 할 것이다.(잘 몰라서 검색했습니다..)

만약 파운데이션 후에 토너를 바른다면? 순서자체가 꼬여버리고, 펙토리는 아에 건설조차도 되지 않습니다.

이런 것 처럼 우리 실생활에는 순서대로 해야하는 과정들이 있는데 그러한 것을 알고리즘화 시키고 프로그래밍화 시킨 것이 위상 정렬이다.

 

위상 정렬(Topological Sort)을 그림을 통해 알아보기

다음과 같은 단방향 그래프가 있다고 생각해보자.

A->C로 가기위해 단계적으로 치루어야 할 것이 있다.

A를 수행해야 B, D를 할 수 있고, C는 B, E가 모두 수행이 완료되야 C를 수행할 수 있게 된다.

A가 완료되고 B, D를 진행할 수 있다.

D가 완료되고 E를 진행할 수 있다. 이때 B가 완료되었다고 C를 진행 할 수는 없다.

 E가 완료되고 비로소야 C를 진행할 수 있다.

이렇게 A->C를 하기위해서는 다음과 같은 과정들을 거쳐야 한다.

이러한 위상 정렬에서는 항상 그래프를 가로로 나열하였을 때, 왼쪽에서 오른쪽으로 모두 방향이 향할 수 있어야 하는데,

사이클을 이루는 경우에는 위상 정렬을 이룰 수 없게된다.

따라서 위상 정렬이 가능하다면 그 그래프는 DAG(Directed Acyclic Graph)의 형태를 띄어야 한다.

이 말은, 방향이 있는 그래프이고, 사이클이 존재해서는 안된다는 의미이다.

위상 정렬(Topological Sort) 구현 방식(BFS를 기준으로 설명)

1. 이 그래프가 사이클이 있는지 확인한다.

(보통의 경우 문제를 해결하는 경우에는 이 과정이 있다면 위상 정렬 자체를 시도하지 않을 것이지만) 

2. 현재 정점에 들어오는 간선이 없다면 BFS라면 큐에 담아준다.

3. 큐에서 front원소를 빼고 front에 연결되어있는 정점들 간의 간선을 모두 삭제해준다. 

이때 해당하는 다음 정점에 들어오는 간선이 없다면 큐에 담아준다.

이 과정을 정점의 개수만큼 반복한다.

4. 결국 이 과정을 반복하는 동안 큐에서 빠지는 front 순서대로가 위상 정렬의 결과이다.

위상 정렬 BFS 구현 코드는 아래 문제를 이용하여 작성하였습니다. 

[2623번] 음악프로그램 :: https://www.acmicpc.net/problem/2623

위상 정렬(Topological Sort) 구현 :: BFS

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

#include <iostream> #include <cstdio> #include <queue>   using namespace std;   vector<int> vc[1001]; // 그래프 형성을 위한 벡터 int line[1001]; // 자신에게 들어오는 간선들의 수 int result[1001]; // 최종 위상 정렬 결과 값   int main() {     int n, m;       scanf("%d %d", &n, &m);       for (int i = 0; i < m; i++)     {         int num, cur, prev;           scanf("%d", &num);           // 피디가 선호하는 순서가 없다면         if (num == 0)             continue;           // prev를 먼저 담아주고 num - 1만큼 반복한다.         scanf("%d", &prev);         for (int j = 0; j < num - 1; j++)         {             scanf("%d", &cur);               // cur은 prev에 의해 들어오는 간선이 생기므로 +1             line[cur]++;             // prev -> cur의 그래프가 생기는 과정             vc[prev].push_back(cur);             // cur이 다음 for문에서 prev가 된다.             prev = cur;         }     }       queue<int> q;       // 들어오는 간선이 없는 정점은 모두 queue에 담아준다.     for (int i = 1; i <= n; i++)         if (line[i] == 0)             q.push(i);       // 위상 정렬     for (int i = 0; i < n; i++)     {         // 위상 정렬 도중에 큐가 비게 된다면 위상 정렬을 할 수 없다.         if (q.empty())         {             printf("0");             return 0;         }           // 큐의 front를 cur로 받아준다.         int cur = q.front();         q.pop();           // 큐에서 front 순서대로가 위상 정렬의 결과 값이다.         result[i] = cur;           // cur->next로 연결되는 노드들에 대해 아래 코드를 수행한다.          for (int j = 0; j < vc[cur].size(); j++)         {             int next = vc[cur][j];             // cur->next의 간선을 지우는 과정, 이때 간선의 수가 0이 되면 큐에 담아준다.             if (--line[next] == 0)                 q.push(next);         }     }       // 위상 정렬 결과 값을 출력한다.     for (int i = 0; i < n; i++)         printf("%d\n", result[i]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus