[개념 정리] 특정 방문 순서가 있는 정렬: 위상 정렬 (개념 및 구현하기)

순서가 정해져 있는 여러 일들을 순서에 맞게 나열할 떄 사용할 수 있는 알고리즘이다. 즉, 선후 관계가 정의된 Graph에서 선후 관계에 따라 정렬 하기위해 위상 정렬을 이용한다. 이 때, Graph는 반드시 비순환 방향 그래프여야 한다. 

선수 과목이 대표적인 예시다. 특정 수강과목에 먼저 수강해야하는 과목이 있다면 해당 과목부터 수강해야 한다. 이 경우, 위상 정렬을 통해 올바른 수강 순서 중 하나를 찾아낼 수 있다.

위상 정렬 동작

진입 간선 수는 Node에 들어오는 간선 수로, 해당 Node 전에 방문해야하는 다른 Node의 수를 의미한다. 

1. 진입 간선 수가 0인 Node와 이와 연결된 모든 (진입, 진출)간선 삭제
2. 남아있는 그래프의 진입 간선 수를 갱신
3. 그래프에 모든 Node가 없어질 때까지 1,2를 반복한다.

위상 정렬 구현

/******************************************************************************
위샹 정렬
*******************************************************************************/

#include <vector>
#include <string>
#include <queue>

using namespace std;

int main() {
    int V, E;  // V: # of vertices, E: # of edges
    // V, E 수 정보
    scanf("%d %d", &V, &E);
    
    vector<vector<int>> edges(V, vector<int>({}));
    vector<int> indegree(V, 0);  // 노드(Vertex) 별 진입 간선 수 저장
    queue<int> q;
    
    for (int i = 0; i < E; i++) {
        int from, to;
        scanf("%d %d", &from, &to);
        // edges[i]에 i에서부터 다음으로 갈 노드 번호 저장
        edges[from].push_back(to);
        // 진입 간선 수 ++ 
        indegree[to]++;
    }
    
    // 진입 간선 수가 0인 모든 노드를 queue에 저장
    for (int i = 0; i < V; i++) {
        if (!indegree[i]) {
            q.push(i);
        }
    }

    while(q.size()) {
        int now = q.front();
        q.pop();
        
        // 현재 노드에서 다음으로 갈 수 있는 노드를 탐색하며
        // 진입 간선 수를 업데이트하고
        // 만약 진입 간선 수가 0이면 queue에 저장
        for (int i =0; i<edges[now].size(); i++) {
            int next = edges[now][i];
            indegree[next]--;
            
            if (!indegree[next]) {
                q.push(next);
            }
        }
    }
}

vector 형태의 indegree는 Node의 개수와 같은 크기로, indegree[i]는 i번 째 Node 전에 우선으로 방문해야하는 Node수를 의미한다. 간선의 연결 정보를 받아 edges에 저장한다. edges[i]는 vector로 i번 째 Node가 다음으로 갈 수 있는 Node를 순서대로 추가한다. 이 때, indegree를 업데이트한다. 그러면 이제 위상 정렬을 이용할 수 있는 준비는 끝이 났고, 위상 정렬을 아래 순서와 같이 진행한다. 

1. queue에 indegree가 0인 Node를 모두 추가한다.
2. queue를 순서대로 추출하면서 해당 Node 연결된 간선 정보는 삭제한다. 
   • 이 때 구현은, 다음으로 갈 수 있는 Node를 확인하고 해당 Node의 indegree 값을 -1하여 구현
3. queue에서 모두 추출될 때까지 반복한다.

사이클이 존재하면, 모든 정점을 돌기 전에 queue의 크기가 0이 된다.