위상 정렬 (TopologySort)

위상 정렬이란?

 

사전 작업, 선행 작업 등 순서가 정해진 작업을 차례대로 수행해야 할 때, 그 순서를 나열한 것.

사이클이 존재하지 않는 방향 그래프의 모든 노드를 순서에 거스르지 않도록 나열한 것.

 

'스타크래프트' 게임을 생각하면 쉽게 이해할 수 있다.

'서플', '배럭'을 짓기 위해서는 선행 작업으로 '커맨트 센터'를 먼저 만들어야 한다.

이 순서를 어기게 되면, 영원히 '서플'과 '배럭'을 건설할 수 없게 된다.

 

이렇듯, 선행이 필수인 것부터 나열해서 정렬하는 것이 위상 정렬이다.

 

위상 정렬의 동작 과정

 

1. 진입 차수가 0인 노드 먼저 큐에 넣는다.
2. 큐가 빌 때까지 반복한다.
   1. 큐에서 원소를 꺼내고, 그 노드에서 출발하는 간선들을 모두 제거한다.
   2. 이때 새롭게 진입 차수가 0인 노드들은 큐에 넣어준다.

큐에서 빠져 나오는 순서가 바로 구하려고 하는 위상 정렬이다.

진입 차수(indegree)는 해당 노드로 들어오는 간선의 수를 의미한다.

 

위상 정렬의 시간 복잡도

 

V : 노드의 수

E : 간선의 수

시간 복잡도 : 인접 리스트로 구현하면 O(V + E)지만, 인접 행렬로 구현하면 O(V^2)

 

차례대로 모든 노드들을 확인하면서 해당 노드에서 출발하는 간선들을 차례대로 제거하므로

결과적으로는 모든 노드와 모든 간선을 확인하기 때문이다.

 

위상 정렬 구현

 

위상 정렬에 필요한 것은 Queue의 자료구조

입력 범위에 따라 인접 행렬, 인접 리스트로 그래프를 구성하고 해결한다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 32000 + 1;

int V, E;
int indegree[MAX];
vector<int> adj[MAX];

void topologySort()
{
    vector<int> ret;
    queue<int> q;
    
    //처음 시작할 때는 진입차수가 0인 노드를 큐에 넣어준다.
    for(int i = 1; i <= V; i++)
    {
        if(indegree[i] == 0)
            q.push(i);
    }
    
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        
        //큐에서 빠져 나온 순서가 정렬 순서
        ret.emplace_back(now);
        
        //해당 원소와 연결된 노드들의 진입차수에서 1빼기
        for(int i = 0; i < adj[now].size(); i++)
        {
            int next = adj[now][i];
            indegree[next]--;
            //새롭게 진입차수가 0이 되는 노드는 큐에 넣어주자.
            if(indegree[next] == 0)
                q.push(next);
        }
    }
    
    for(const auto& i : ret)
    {
        cout << i << ' ';
    }
    cout << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> V >> E;
    for(int i = 0; i < E; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        indegree[b]++;
    }
    
    topologySort();
    
    return 0;
}

한 걸음 더 나아가서

 

위상 정렬 도중에 큐가 비게 된다는 것은 사이클이 존재한다는 것을 의미한다.

운영체제 시간에 배운 순환 대기 형태를 생각해보면 이해하기 쉽다.

 

이렇게 순환 대기 형태를 이루게 되면(사이클을 이루게 되면) 순환 대기 형태를 띠는 노드들은 진입 차수가 0이 될 수 없으므로,

위상 정렬 큐에 들어가지 못하고 중간에 끝나버리게 된다.

 

앞서 말했듯이 위상 정렬은 모든 노드들과 모든 간선을 확인해야 하는데,

모든 노드를 탐색하기도 전에 큐가 empty 형태가 되어 끝나버리게 되는 것이다.

 

즉, 이러한 사이클 구조를 발견하기 위해서는 모든 노드를 탐색하기 전에 정렬이 끝나버리는 것을 체크하면 해결할 수 있다.

void topologySort()
{
	vector<int> ret;
	priority_queue<int, vector<int>, greater<int> > q;

	for (int i = 1; i <= v; i++)
	{
		if (indegree[i] == 0) q.push(i);
	}

	for (int i = 1; i <= v; i++)
	{
		// 위상 정렬 도중에 큐가 비게 된다면 사이클이 존재한다는 의미
		if (q.empty())
		{
			cout << -1 << '\n';
			return;
		}

		int now = q.top(); q.pop();
		ret.push_back(now);

		for (int i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i];
			indegree[next]--;
			if (indegree[next] == 0) q.push(next);
		}
	}

	for (int n : ret) cout << n << '\n';
}

 

위상 정렬의 답은 1개가 아니다?

 

때로는 위상 정렬의 답은 여러개가 될 수 있다.

진입 차수가 0이 되는 노드가 2개 이상이 큐에 들어가는 경우가 발생하면 여러 가지 답이 나올 수 있다.