알고리즘 스터디

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

문제

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

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

입력

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

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

 

 

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

원래 Google Kick Start Round C의 3번째 문제를 풀 생각이었는데

아무리 고민해봐도 답이 안나와서 검색해보다가 '위상정렬' (topological sort)를 알게 되었어요.

바로 킥스타트 풀기 보다는 위상정렬에 조금 친숙해진 뒤에 풀어볼 생각으로 백준에서 관계된 문제를 먼저 풀어봤습니다.

 

C++를 사용한 제 풀이입니다.

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

using namespace std;
int n, m;
vector<vector<int>> a(32001, vector<int>(0));
vector<int> b(32001, 0);
queue<int> q;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	int t1 = 0, t2 = 0;

	for (int i = 1; i < m + 1; ++i) {
		cin >> t1 >> t2;
		a[t1].push_back(t2);
		++b[t2];
	}

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

	while (!q.empty()) {
		int t = q.front();
		q.pop();
		cout << t << " ";
		for (int i = 0; i < a[t].size(); ++i) {
			--b[a[t][i]];
			if (b[a[t][i]] == 0) {
				q.push(a[t][i]);
			}
		}
	}
}

각 숫자에 해당하는 인덱스를 가진 이차원벡터 a를 만들고

각 숫자에 incoming node 갯수를 저장할 b 벡터를 만들어서

incoming node 갯수가 0개인 숫자들을 각각 queue에 집어넣고

queue의 앞에있는 숫자를 이차원 벡터 a의 인덱스로 줘서 다음노드들을 찾아 b에서 빼주는 식으로 풀었어요

밥먹고 이것저것 하고 찾고 하느라고 시간은 2시간정도 걸린 것 같은데 

위상 정렬 관련된 문제들을 더 풀면서 익숙해지고 난뒤에 kickstart를 다시 재도전 해봐야 될 것 같네요