[백준] 2252-줄 세우기

[조건]

- 시간 제한:  문항, 2초

- Stack: 128MB

 

[문제]

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

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

- 학생의 수: 1 ≤ N ≤ 32,000

- 비교 횟수: 1 ≤ M ≤ 100,000

 

[접근법]

알고리즘은 기본 개념과 어떻게 문제에서 응용되는지를 알아야 한다.

"순서가 있는 일을 순서에 맞게 나열한다" 는 기본 개념을 잊지 않았다면 본 시험에서 적용해 봤을텐데..

아쉽기만 하다.

 

[알고리즘]

위상정렬

▷유사문제: 

 

[구현코드]

// 2252_줄세우기.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

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

const int MAX_N = 32001;

int indegree[MAX_N];
vector<int> v[MAX_N];

int main()
{
	int n, m, a, b;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &a, &b);
		indegree[b]++;
		v[a].push_back(b);
	}

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

	while (!q.empty()) {
		int now = q.front();
		q.pop();

		printf("%d ", now);

		for (const auto &conn : v[now]) {
			if (--indegree[conn] == 0) {
				q.push(conn);
			}
		}
	}
}