[백준]줄 세우기(2252)

문제 링크 : [백준]줄 세우기(2252)

2252번: 줄 세우기

문제 설명

N명의 학생을 키 순서에 맞추어 줄을 세우려고 합니다.

하지만 주어지는 데이터는 두 학생들간의 대소 비교가 M개만큼만 주어집니다.

M개의 두 학생간의 비교 데이터만 가지고 키 순서대로 줄을 세우세요.

입력

N(학생의 수, 1 <= N <= 32,000)

M(비교 결과의 수, 1 <= M <= 100,000)

A_i B_i(두 학생의 키 비교 결과, A_i < B_i)

3 2
1 3
2 3

 

출력

1 2 3

 

카테고리

#위상정렬

 

시간 복잡도 상한

O(NlogN) 혹은 O(MlogM)

 

해결 방법

1. 작은 사람부터 줄을 세워야 하기 때문에, 자기보다 큰 사람이 없는 사람을 먼저 출력합니다.
2. 단, 그런 사람이 여러명일 수 있는데, 그럴 때는 아무거나 출력해도 된다고 했으니 인덱스가 작은 사람부터 출력합니다.
3. 1번에서 대상이 된 사람을 다 출력했다면, 그 사람들보다 큰 사람들 중 그 외 사람들보다 큰 사람이 없는 사람들을 출력합니다.
4. 쉽게 말해서 1번에서 1, 2번이 출력됐다면, 1번과 2번 보다 큰 사람만 출력합니다.(3번이나 4번 등 다른 사람보다 큰 사람은 제외합니다.)
5. 그 이유는 앞에 출력된 사람들 외에 다른 사람보다 더 큰 경우가 있다면, 그 사람보다 뒤에 서야하기 때문에 그 사람이 출력된 후에 출력되어야 합니다.
6. 즉 자신보다 작은 사람들이 다 출력이 된 이후에 자신이 출력되어야 합니다.
7. 이것을 그래프로 나타내게 되면 자신에게 들어오는 In-bound가 0인 노드부터 출력하여, 그 노드에 연결된 노드의 In-bound를 하나씩 줄여 나가 0이 되는 순간 출력해주면 됩니다.
8. 즉, 위상정렬을 통하여 해결하면 됩니다.

시간복잡도

O(M)

코드

#include <cstdio>
#include<vector>
#include<queue>
using namespace std;
vector<int> v[32002];
queue<int> dq;
int N, M, position, to;
int x, y;
int ind[32002];

int main() {
	scanf("%d %d", &N, &M);
	for (int index = 0; index < M; index++) {
		scanf("%d %d", &x, &y);
		v[x].push_back(y);
		ind[y]++;
	}
	
	for (int index = 1; index <= N; index++) {
		if (ind[index] == 0) {
			dq.push(index);
		}
	}

	while (!dq.empty()) {
		position = dq.front();
		dq.pop();
		printf("%d ", position);
		for (int index = 0; index < v[position].size(); index++) {
			to = v[position][index];
			ind[to]--;
			if (ind[to] == 0) {
				dq.push(to);
			}
		}

	}
}