위상 정렬 (topology sort)

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.

 

• 기능 : 노드 간의 순서를 결정
• 특징 : 사이클이 없어야 한다.
• 시간 복잡도 : O(V + E)

위상 정렬은 항상  유일한 값으로 정렬되지 않는다.

또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.

순서를 찾는 알고리즘이므로 무방향 그래프에서는 적용할 수 없다.

 

위상 정렬의 원리

 

백준 2252: 줄 세우기

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

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graph;
vector<int> inDegree;
vector<bool> visited;
vector<int> answer;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	graph.resize(N + 1);
	inDegree.resize(N + 1);
	visited.resize(N + 1, false);

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		inDegree[b]++;
	}

	//위상 정렬
	while (true)
	{
		int cur;
		//진입 차수가 0인 노드 찾기
		for (int i = 1; i <= N; i++)
		{
			if (inDegree[i] == 0 && !visited[i])
			{
				cur = i;
				//정답 배열에 넣기
				answer.push_back(cur);
				visited[i] = true;
				break;
			}
		}
		//모든 노드를 정렬한 경우 반복문 탈출
		if (answer.size() == N)
			break;

		//0인 노드와 인접한 노드의 차수 1 내리기
		for (int node : graph[cur])
		{
			inDegree[node]--;
		}
	}

	for (int node : answer)
	{
		cout << node << " ";
	}

	return 0;
}

 

이 문제는 학생들을 노드로 하고 키의 비교를 간선으로 해서 그래프로 표현한 뒤 순서를 나타내는 것이므로 위상 정렬을 적용하면 되는 문제이다.

문제를 해석하고 적용할 알고리즘을 떠올리면 맞출 수 있을 것 같다.

지금 내 구현에서는 반복문을 돌면서 진입 차수가 0인 노드를 찾는데, 다른 풀이를 찾아보니까 BFS처럼 큐를 활용해서 깔끔하게 구현할 수 있었다.(방문 배열을 없앨 수 있음)

 

백준 1516번 : 게임 개발

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> graph;
vector<int> inDegree;
vector<int> bulidTimes;
vector<int> answer;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	graph.resize(N + 1);
	inDegree.resize(N + 1, 0);
	bulidTimes.resize(N + 1, 0);
	answer.resize(N + 1, 0);

	for (int i = 1; i <= N; i++)
	{
		cin >> bulidTimes[i];
		while (true)
		{
			int data;
			cin >> data;
			if (data == -1)
				break;

			graph[data].push_back(i);
			inDegree[i]++;
		}
	}
	
	//위상 정렬
	queue<int> Q;
	
	for (int i = 1; i <= N; i++)
	{
		if (inDegree[i] == 0)
		{
			Q.push(i);
		}
	}

	while (!Q.empty())
	{
		int cur = Q.front();
		Q.pop();

		for (int node : graph[cur])
		{
			inDegree[node]--;
			//max를 하는 이유는 여러 선행 건물 중에 오래 걸린 시간을 기준으로 해야
			//중첩된 선행 건물의 경우 시간이 무시되지 않을 수 있다.
			answer[node] = max(answer[node], answer[cur] + bulidTimes[cur]);
			if (inDegree[node] == 0)
			{
				Q.push(node);
			}
		}
	}

	for (int i = 1; i <= N; i++)
	{
		//자기 건물 짓는 시간 더하고 출력
		answer[i] += bulidTimes[i];
		cout << answer[i] << '\n';
	}
	return 0;
}

 

이 문제는 max 함수를 써야 한다는 아이디어가 없었어서 처음에 틀렸다.

선행 건물이 두 개 이상 있는 경우 max를 하지 않으면 더 적은 시간이 걸린 선행 조건의 건물의 시간이 정답 배열에 들어 갈 수 있으므로 max를 써서 큰 값을 넣어야 한다.

위상 정렬을 적용해야 할 수 있는 근거는 건물 짓는 순서가 존재하고 사이클이 생기지 않기 때문이다.(방향 비순환 그래프)

 

공부 자료 : Do it! 알고리즘 코딩테스트 C++ (김종관, 이지스 퍼블리싱)