boj, 백준) 2252. 줄 세우기 ( C / C++ )

1. 문제 링크

www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

2. 문제 개요

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 했다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

 

3. 문제 힌트

위상 정렬을 사용해보자.

 

 

4. 문제 풀이

문제를 푼 사람도 많고, 정답률도 높아서 포스팅을 안 하려고 했는데, 문제가 워낙 기본적이고 모든 위상 정렬 문제의 기초가 되는 문제라 정리할 겸 포스팅했습니다.

 

일의 순서, 즉 키의 순서를 정렬할 때, 위상정렬 알고리즘을 사용해야 한다.

 

우선, 그래프가 DAG(유향 비순환 그래프, Directd Acyclic Graph)인지 확인해야 한다.

시간복잡도도 체크해보자.

O(V+E)시간에 충분히 처리된다.

 

 

위상정렬은 말 그대로 위상으로 정렬하는 방법이다.

대신에 흔히 말하는 차수(degree)가 위상이 된다. 여기서는 자신으로 들어오는 간선의 개수만 센다.

 

모든 정점(학생)의 위상(차수)을 확인하면서 위상이 0인 노드들을 Queue에 담자. (O(V)소요)

그런 뒤, 위상이 0인 정점들로부터 뻗어 나가는 간선들을 제거한다.

제거함에 따라, 연결되는 정점들의 위상을 1 감소시킨다. 이때 해당 정점의 위상이 0이 되는지 체크하고 0이 되면 queue에 넣어주고 그렇지 않으면 그냥 넘어가자.

 

이렇게 queue가 텅 빌 때까지 반복하면 된다.

모든 정점들이 0이 될 때까지 확인하고, 모든 간선들을 지우기 때문에 O(V) + O(E)가 된다.

 

 

5. 코드

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

queue<int> q;
vector<int> v, ans;	//degree(topology)
vector<vector<int>> adj;
int n, m;

int main()
{
	scanf("%d %d", &n, &m);
	v.resize(n + 1);
	adj.resize(n + 1);

	for (int i = 0; i < m; ++i) {
		int to, from;
		scanf("%d %d", &to, &from);

		adj[from].push_back(to);
		++v[to];	//degree
	}

	for (int i = 1; i <= n; ++i) 
		if (v[i] == 0) 
			q.push(i);
		
	while (!q.empty()) {
		int cur = q.front(); q.pop();

		for (int next : adj[cur])
		{
			--v[next];

			if (v[next] == 0) 
				q.push(next);
		}
		ans.push_back(cur);
	}

	for (int i = ans.size() - 1; i >= 0; --i)
		printf("%d ", ans[i]);


	return 0;
}

 

6. 결과