[Baekjoon] 2252번: 줄세우기

🥅 문제

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

 

🔍 설계

두 노드 간의 순서가 정해져 있고, 답이 여러가지인 경우에는 아무거나 출력하라는 것에서 전형적인 위상 정렬임은 쉽게 파악할 수 있었다. 다만, 다시 기억시키기 위해 알고리즘 파트에 정리하였다.

 

👊 풀이

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

int n, m, a, b;
vector<int> degree(32001);
vector<vector<int>> graph(32001);

void topology_sort() {
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (degree[i] == 0) {
			q.push(i);
		}
	}

	while (!q.empty()) {
		int cur_x = q.front();
		q.pop();
		cout << cur_x << " ";
		int size = graph[cur_x].size();
		for (int i = 0; i < size; i++) {
			int next_x = graph[cur_x][i];
			degree[next_x] -= 1;
			if (degree[next_x] == 0) {
				q.push(next_x);
;			}

		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		degree[b] += 1;
		graph[a].push_back(b);
	}

	topology_sort();

	return 0;
}

 

✍️알고리즘

위상 정렬은 노드 간에 순서가 정해져 있을 때, 나열하거나 작업을 처리하는 상황에서 정렬하는 알고리즘이다.

 

위상 정렬은 DAG(Directed Acyclic Graph)에서만 가능하다. 양방향이거나 사이클이 있으면, 우선순위가 없는 것과 같다.

 

구현하는 방법은 다음과 같다.

 

1. 각 노드마다 진입 차수를 기록한다. 우선순위가 낮다면 진입 차수를 증가시킨다. 진입 차수가 0이 되었을 때, 그 노드를 이용할 수 있다.

2. 진입 차수가 0인 노드를 큐에 담고, 하나씩 꺼내면서 연결된 노드들의 진입 차수를 1씩 줄인다. 꺼낸 노드가 사용되어 사라지면서 선행되어야 할 것이 하나 줄었기 때문이다. 연결된 노드들의 진입 차수가 0이라면 큐에 담는다.

 

이 과정을 반복한다.