[BOJ-2252] 줄 세우기(C++)

백준 2252 줄세우기

 

 

2252번: 줄 세우기

 

 

문제 설명

 

 - N명의 학생들을 키 순서대로 줄을 세우려 한다.

 

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

 

 - 첫째 줄에 학생들을 키 순서대로 세운 결과를 출려하라.

   답이 여러 가지인 경우에는 아무거나 출력한다.

 

---

 

입력 값

 

 - 첫째 줄에 N, M이 주어진다.

  ( 1<= N <= 32,000 / 1 <= M <= 100,000 )

 

 - 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 

   학생 A가 학생 B 앞에 서야 한다는 의미다.

 

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

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 주어진 순서를 바탕으로 전체 순서를 찾아보는 문제이다.

 

 - 두 명의 키 순서가 주어진다. 

   즉, 키 순서대로 줄을 세우기 위해서는 키 큰 사람은 자신보다 작은 사람이 반드시 앞에 있어야 한다.

 

 - 결론적으로 이 문제는 위상 정렬을 이용한 문제이다.

위상 정렬(Topological Sort)

 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

// height[i] = i보다 키 큰 사람의 번호
vector<int> height[32001];

// heightCnt[i] = i보다 작은 사람의 수
int heightCnt[32001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	
	cin >> N >> M;

	for (int i = 0; i < M; i++) {

		int A, B;
		cin >> A >> B;
		height[A].push_back(B);
		heightCnt[B]++;
	}

	queue<int> q;

	for (int i = 1; i <= N; i++) {
		if (heightCnt[i] == 0) {
			q.push(i);
		}
	}
	vector<int> result;

	while (!q.empty()) {

		int nowIndex = q.front();
		q.pop();

		result.push_back(nowIndex);

		for (int nextIndex : height[nowIndex]) {

			heightCnt[nextIndex]--;

			if (heightCnt[nextIndex] == 0) {
				q.push(nextIndex);
			}

		}
	}

	for (auto h : result) {
		cout << h << " ";
	}
	cout << "\n";

	return 0;
}