[C++][백준] 줄 세우기(2252)

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

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

 

입력

첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

 

출력

첫째 줄부터 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

 

풀이

문제의 조건을 정리하면 아래와 같습니다.

(1) 두 학생의 번호 A, B가 주어질 때 학생 A는 학생 B의 앞에 서야 합니다.

(2) M번의 비교 후 앞에서부터 줄을 세운 결과를 출력합니다.

 

이 처럼 순서가 정해져 있는 작업(1) 을 차례로 수행할 때(2) 위상정렬 알고리즘을 사용합니다. 

위상정렬 알고리즘을 활용할 필요없이, 단순 위상정렬 알고리즘 결과 자체가 답이 됩니다.

 

위상정렬에 대한 상세 내용은 Reference에서 확인하실 수 있습니다.

간단한 특징은 아래와 같습니다.

1. 위상정렬은 여러개의 답이 존재할 수 있습니다.

2. 사이클이 발생하지 않는 방향 그래프에만 적용 가능합니다.

 

위상정렬은 일반적으로 Queue 자료구조를 통해 구현합니다.

1. 진입차수가 0인 정점을 Queue에 삽입한다.

2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.

3. 간선 제거 이후 진입차수가 0인 정점을 Queue에 삽입한다.

4. Queue가 빌때까지 2~3 과정을 반복한다.

 모든 원소를 방문하기 전에 Queue가 빈다면 사이클이 존재하는 것이고

 모든 원소를 방문했다면 Queue에서 꺼낸 순서가 위상 정렬의 결과이다.

 

모든 원소를 방문하기 전에 Queue가 빈다면 왜 사이클이 존재하는것인지 헷갈리실 분들을 위해 그림을 준비했습니다.

 

먼저 모든 원소는 Queue에 한번 들어갔다가 한번 빠져나오기 때문에 N번 Queue에서 pop연산을 수행합니다.

사이클이 존재하는 그래프에서 진입차수가 0인 정점을 Queue에 삽입하였습니다.

 

 

큐에서 원소를 꺼내 연결된 모든 간선을 제거합니다.

간선 제거 이후 진입차수가 0인 정점을 Queue에 삽입하려고 하지만 진입차수가 0인 정점이 존재하지 않습니다.

이처럼 사이클이 존재하는 경우 Queue에서 N번 pop하기 전에 Queue가 비어버리게 됩니다.

 

그러나 줄세우기 문제와 같은 경우 사이클이 존재하지 않음이 보장되기 때문에 조건처리를 따로 하지 않았습니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 33000;
vector<int> myGraph[MAX];
int inDegree[MAX];
int n, m; // n : 학생 수, m : 비교 횟수

void topoloySort() {
	queue<int> myQueue;
	// 진입 차수가 0인 정점을 queue에 넣는다.
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) {
			myQueue.push(i);
		}
	}

	for (int i = 1; i <= n; i++) {
		int cur = myQueue.front();
		myQueue.pop();
		printf("%d ", cur);

		for (int j = 0; j < myGraph[cur].size(); j++) {
			int next = myGraph[cur][j];
			inDegree[next] -= 1;
			if (inDegree[next] == 0) {
				myQueue.push(next);
			}
		}
	}
}

int main() {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int first, second;
		cin >> first >> second;

		myGraph[first].push_back(second);
		inDegree[second]++;
	}

	topoloySort();

	return 0;
}

 

 

 

---

Reference

 

blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)