[Algorithm] 위상정렬 / Topological Sort

1. 위상정렬이란?

• 순환하지 않고 방향이 정해져있는 그래프의 노드를 거스르지 않은 상태로 정렬하는 방법.
• 비순환 유향 그래프에서만 사용할 수 있으며 순환이 있거나 양방향 그래프에 대해서는 사용하지 못한다.
• 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저오는 순서로 정렬이 된다.
• 시간 복잡도 : O(V+E) {Vertex : 노드의 갯수 /  Edge : 간선의 갯수}

---

2. Default Logic

위상정렬을 하는 방법에는 BFS를 사용하는 방법과 DFS를 사용하는 방법이 있는데 나는 BFS로 설명할 것이다.

 

먼저 BFS를 사용한 방법을 말로 설명해 보자면

1. 모든 정점의 inDegree를 설정해준다. (inDegree : 정점으로 들어오는 간선 수)

2. 한 간선을 처리한 후 inDegree를 --해준다.

3. inDegree가 0인 정점은 방문한 것으로 표시하고 큐에 정점을 추가한다.

4. 이후 큐가 빌때까지 반복한다.

 

아래 코드와 같이 보면 이해가 훨씬 빠를것이다.

#include<bits/stdc++.h>

using namespace std;

#define MAX_VALUE = 5

vector<int> graph[10];
//정점으로 이어진 간선 수
int inDegree[10];

void topologicalSort() {
    queue<int> q;

	//노드를 처음부터 끝까지 순회하면서
    //inDegree(자기한테 들어오는 간선의 갯수)값이 0인 노드만 queue에 넣는다.
    for(int i = 1; i <= MAX_VALUE; i++) {
        if(!inDegree[i])
            q.push(i);
    }

    while(!q.empty()) {
        int cur = q.front();
        q.pop();
		
        //inDegree값이 0이면 
        cout << cur << " ";

        for(int i = 0; i < graph[cur].size(); i++) {
            inDegree[graph[cur][i]]--;
            //간선을 하나씩 처리하면서 inDegree값이 0이면 queue에 push
            if(!inDegree[graph[cur][i]]) {
                q.push(graph[cur][i]);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    //Value Input
    graph[1].push_back(2);
    inDegree[2]++;
    graph[1].push_back(3);
    inDegree[3]++;
    graph[2].push_back(4);
    inDegree[4]++;
    graph[3].push_back(4);
    inDegree[4]++;
    graph[4].push_back(5);
    inDegree[5]++;

	//위상정렬
    topologicalSort();
}

그림을 통해 이해를 돕자면

 

1. 값을 입력받으면서 그래프로 서로 관계를 지어줌과 동시에 진입차수(inDegree)를 count 해준다.

 

 

2. 1 ~ 5까지 순회하며 Indegree가 0인 값에 대해서만 queue에 넣어준다. 예시에서는 1번 노드에 대해서만 1번노드로 들어오는 간선이 없기 때문에 queue에 1을 넣어준다.

3. 1번 노드와 연결된 노드들을 탐색하면서 진입차수를 1 줄여준다. 다음 노드의 진입차수를 하나 줄여주는 이유는 다음 노드로 가는 간선을 탐색했고 다시는 이전 노드를 탐색하면 안되기 때문에 중복을 줄여주기 위해 1 줄여주는 것이다. 이때 2번 노드를 먼저 탐색 하고 현재 2번 노드로 들어오는 간선이 없기 때문에(inDegree 값이 0) 2번 노드를 queue에 넣어준다.

아래의 코드에서 이러한 로직이 동작한다.

for(int i = 0; i < graph[cur].size(); i++) {
            inDegree[graph[cur][i]]--;
            if(!inDegree[graph[cur][i]]) {
                q.push(graph[cur][i]);
            }
        }

4. 3번노드도 동일하게 진행해준다.

 

5. 4번 노드로 들어오는 간선의 갯수는 2개인데 이 중 먼저 queue에 들어온 2부터 처리한다. queue에서 2를 빼주고 2번 노드에서 4번 노드로 가는 간선을 탐색했기 때문에 4번 노드의 진입차수에서 1을 빼준다. 하지만 아직 진입차수가 0이아니고 1이기 때문에 4번 노드를 queue에 push해주지는 않는다.

6. queue에 들어와있는 3번 노드를 검사하면서 4번 노드의 진입차수를 1빼준다. 이때 드디어 4번 노드의 진입차수가 0이 되므로 4번 노드를 queue에 넣어준다.

7. queue에 있는 4번 노드와 연결되어있는 5번 노드를 검사하고 5번 노드의 진입차수를 이전의 과정과 동일하게 1 빼준다. 그럼 진입차수가 0이기 때문에 또 queue에 넣어준다.

8. 마지막 노드에 들어가서 탐색하고 이후에 연결되어 있는 노드가 없기 때문에 queue에 아무것도 들어가지 않아 while문 기저조건에 걸리기 때문에 함수가 종료된다.

---

3. 추천 문제

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

2252번: 줄 세우기

 

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

1766번: 문제집

---