[알고리즘] 위상 정렬(Topological Sorting)

1. 개요 및 대표 문제

1. 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘
2. 사이클이 없는 방향 그래프(Direct Acyclic Graph)에서만 수행
3. 시간 복잡도 = O(V + E) 

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

2252번: 줄 세우기

 

2. 위상 정렬의 대표 예시

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

 위의 이미지처럼 작업의 순서가 정해져 있을 때 작업을 정렬해주는 알고리즘이 바로 '위상 정렬'이다.

위상 정렬 결과

대학생 되기 → 학과 사이트 가입하기 → 4학년 되기 → 정보처리기사 합격하기 → 자격 서류 제출하기 → 졸업시험 신청하기 → 졸업하기

 

3. 진입 차수와 진출 차수

• 진입 차수(Indegree) : 특정한 노드로 들어오는 간선의 개수
• 진출 차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수

출처 : https://velog.io/@kimdukbae/%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-Topological-Sorting

 

4. 위상 정렬 알고리즘 동작 과정

1. 진입 차수가 0인 노드를 큐에 삽입
2. 큐가 빌 때까지 다음의 과정을 반복
    1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거(진입 차수 1씩 감소)
    2) 새롭게 진입 차수가 0이 된 노드를 큐에 삽입

출처 : https://velog.io/@kimdukbae/%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-Topological-Sorting

 

[최종 결과] 1 → 2 → 5 → 3 → 6 → 4 → 7

5. 위상 정렬의 특징

• 사이클이 없는 방향 그래프(Direct Acyclic Graph)에서만 수행 가능
• 여러가지 답이 존재 가능
• 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재
• 보통 Queue로 구현하나, Stack을 이용한 DFS를 이용해 위상 정렬 구현 가능

 

6. 위상 정렬 알고리즘 코드

 1) Queue 방식

• 관련 문제 : https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

#include <iostream>
#include <vector>
#include <queue>
#define MAX_N 32001

using namespace std;

int N, M;
int visited[MAX_N];
int inDegree[MAX_N];
vector<int> graph[MAX_N];
vector<int> path;

// 위상 정렬 알고리즘
void topological_sort()
{
	// 모든 노드 탐색 
	for (int i = 1; i <= N; i++)
	{
		// 진입차수가 0이 아니거나, 이미 방문한 노드이면 건너뛰기
		if (inDegree[i] || visited[i]) continue;

		queue<int> q;

		visited[i] = 1;	// 방문 체크
		q.push(i);	// Queue에 추가

		// Queue 빌때까지 탐색
		while (!q.empty())
		{
			int cur = q.front();
			q.pop();
			path.push_back(cur);	// 경로 추가

			// 해당 노드의 간선 탐색
			for (int j = 0; j < graph[cur].size(); j++)
			{
				int next = graph[cur][j];

				// 이미 방문했거나, 차감한 진입차수가 0이 아니면 건너뛰기
				if (visited[next] || --inDegree[next] != 0) continue;

				visited[next] = 1;	// 방문 체크
				q.push(next);	// Queue에 추가
			}
		}
	}
}

int main()
{
	// IO 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// N : 학생 수, M : 키를 비교한 횟수
	cin >> N >> M;

	// 키를 비교한 결과 입력
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;

		graph[a].push_back(b); // 그래프 추가
		inDegree[b]++; // 진입차수 추가
	}

	// 위상 정렬 알고리즘
	topological_sort();	

	// 정렬된 결과 출력
	for (auto item : path)
		cout << item << " ";

	return 0;
}

 

 2) Stack 방식(DFS 방법)

void topologicalSort_DFS (Graph *G) {
  int i = 0;
  AdjListNode *temp = NULL;
  Stack *S = createStack(G->vertexNumber);

  // 모든 정점을 순회하며 방문하지 않은 정점에 대해서 DFS를 수행
  for (i = 0; i < G->vertexNumber; i++) {
    if (!visitied[i]) {
      DFS(G,i,S);
    }
  }
  
  // 위상 정렬된 위상 순서를 출력한다.
  printStack(S);
}

void DFS (Graph *G, int v, Stack *S)
{  
  AdjListNode *temp = NULL;
  
  visitied[v] = 1;
  
  // 재귀를 통해 방문하지 않은 인접 정점으로 이동한다.
  for (temp = G->adj[v].head; temp != NULL; temp=temp->next) {
    if (!visitied[temp->dest])
      DFS(G,temp->dest,S);
  }
  // 더이상 방문할 간선이 없다면 리스트 앞에 정점을 추가한다.
  push(S, v);
}

 

3) Priority Queue 방식

• 관련 문제 : https://www.acmicpc.net/problem/1766

1766번: 문제집

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX_N 32001

using namespace std;

int N, M;
int visited[MAX_N];
int inDegree[MAX_N];
vector<int> graph[MAX_N];
vector<int> path;

// 위상정렬
void topologicalSort()
{
	// 모든 노드 탐색
	for (int i = 1; i <= N; i++)
	{
		// 진입차수가 0이 아니거나, 이미 방문한 노드이면 건너뛰기
		if (inDegree[i] || visited[i]) continue;

		priority_queue<int, vector<int>, greater<int>> q;

		visited[i] = 1;	// 방문 체크
		q.push(i);  // Queue에 추가

		while (!q.empty())
		{
			int cur = q.top();
			q.pop();	
			path.push_back(cur);	// 경로 추가

			// 해당 노드의 간선 탐색
			for (int j = 0; j < graph[cur].size(); j++)
			{
				int next = graph[cur][j];

				// 이미 방문했거나, 차감한 진입차수가 0이 아니면 건너뛰기
				if (visited[next] || --inDegree[next] != 0) continue;

				visited[next] = 1;	// 방문 체크
				q.push(next);	// Queue에 추가
			}
		}
	}
}

int main()
{
	// IO 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// N : 문제의 수, M : 정보의 개수
	cin >> N >> M;

	// 정보들 입력
	for (int i = 0; i < M; i++) 
	{
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);	// 그래프 추가
		inDegree[b]++;	// 진입차수 추가
	}

	// 위상정렬 알고리즘
	topologicalSort();

	// 정답 출력
	for (int i = 0; i < path.size(); i++)
		cout << path[i] << " ";

	return 0;
}

 

7. 문제

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

1005번: ACM Craft

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

2252번: 줄 세우기

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

2623번: 음악프로그램

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

1766번: 문제집