[알고리즘 공부]위상 정렬

0. 개요

알고리즘 공부를 하면서 문뜩 내가 백준에 문제 읽자마자 바로 포기한 게 뭔가 궁금해졌다.

그래서 좀 뒤져보니 위상정렬 문제는 손도 못대고 보통 포기했다는 걸 알게 되었다.

그래서 이번에는 위상정렬이 무엇이고 어떻게 구현하는 것인지 공부해보았다.

 

1. 알고리즘 개념

위상 정렬 알고리즘은 순서가 정해진, 방향성이 있는 비순환 그래프를 나열하는 알고리즘이다.

라면 레시피처럼 방향성이 있고, 비순환인 경우에만 사용할 수 있다.

대표적인 예로 백준의 줄 세우기 문제가 있다.

 

2. 알고리즘 구조

위상 정렬 알고리즘에서 가장 중요한 개념은 바로 진입 차수(어떤 노드로 들어오는 간선 개수)이다.

위의 예시를 보았을 때, 2번 노드는 진입 차수가 2이며, 0번과 1번 노드는 진입 차수가 0이다.

이 상태에서 위상 정렬 알고리즘은 진입 차수가 0인(선제 조건이 없거나, 이미 만족한) 노드를 하나씩 제거하며 정렬을 수행한다.

더 정확한 예시는 다음과 같다.

1) 그래프 세팅

각 노드에서 나가는 노드와, 해당 노드의 진입 차수를 저장한다.

2) 진입 차수가 0인 모든 노드를 큐에 삽입

이미 조건이 만족 되었거나 선제 조건이 없는 경우 후보로 등록한다.

3) 큐에서 노드를 꺼내 결과 리스트에 추가

후보 큐에 있는 노드를 꺼내 다음 순서로 등록한다.

4) 해당 노드에서 나가는 간선 제거, 연결된 노드의 진입 차수 감소

꺼낸 노드로부터 나가는 간선을 제거하여 새로운 후보를 등록한다.

다시 2번 단계로 돌아가 후보 큐가 빌 때까지 진행한다.

 

예시 코드는 다음과 같다.

#include <vector>
#include <queue>

using namespace std;

int main()
{
	int n, m; // n은 노드 개수, m은 간선 개수
	scanf_s("%d %d", &n, &m);

	// 노드는 0부터 시작한다고 가정
	vector<vector<int>> graph(n); // 연결된 노드 그래프
	vector<int> indegree(n); // 진입 차수

	// 그래프 세팅
	for (int i = 0; i < n; ++i)
	{
		int s, e;
		scanf_s("%d %d", &s, &e);
		graph[s].push_back(e);
		++indegree[e];
	}

	queue<int> q; // 후보큐
	for (int i = 0; i < n; ++i)
		if (indegree[i] == 0) q.push(i);

	vector<int> result; // 결과

	while(q.empty() == false) 
	{ 
		int node = q.front();
		q.pop();
		result.push_back(node);

		for (int i = 0, size = graph[node].size(); i < size; ++i)
		{
			// 진입 차수 조정
			--indegree[graph[node][i]];

			// 새로운 후보 등록
			if (indegree[graph[node][i]] == 0)
				q.push(graph[node][i]);
		}
	}

	// 결과값이 노드 수와 다르면 위상 정렬이 불가능 하다는 뜻
	if (result.size() != n)
	{
		printf("위상 정렬 불가능");
		return 0;
	}

	for (int i = 0; i < n; ++i)
	{
		printf("%d  ", result[i]);
	}

	return 0;
}

 

3. 후기

알고리즘 공부의 놀라운 점은 항상 어려워 보이는 문제도 사실 생각해보면 간단한 해답이 있다는 걸 알 수 있다는 거다.

특히 이번 위상 정렬을 공부하면서 에? 이렇게 간단하게?? 라는 생각이 들었다.

어쩌면 우리도 인생에서 문제를 마주했을 때, 겁부터 먹고 해답을 찾으려는 생각조차 하지 않고 회피했던 건 아닐까?

많은걸 느끼게 해준 공부였다.

 

4. 참고 사이트

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

https://m.blog.naver.com/ndb796/221236874984