[C++] G3 백준 2252 - 줄 세우기(클래스5)

1. 문제 링크

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

소요 시간 : 18분

시도 횟수 : 1

 

2. 문제 설명

난이도 : G3

사용 알고리즘 : DFS

일부 학생들의 키를 비교한 대로 가능한 키 순서 중 하나를 출력하는 문제

 

3. 풀이 방식 및 해결

뭔가 정렬을 해야 할 것 같은데 마땅히 떠오르는 방법이 없었다.

내가 아는 방법으로 풀어보고자 했고,

해당 학생보다 먼저 출력되어야 하는 학생 번호를 저장해놓고 DFS 돌리면 되지 않을까?

라는 생각으로 접근을 했었다.

사실 좀 쫄렸다. 골드 3의 난이도에 n은 32000까지라 이 방법이 맞을까? DFS로 안되면 다른 정렬 방법이 뭐가 있을까..?

이런 불안한 마음가짐으로 문제를 풀었고, 코드도 37줄 정도에 고민할 것도 많이 보이지 않아서 걱정했지만 웬걸 바로 맞아버렸다.

 

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

bool isvisit[32001];
unordered_map<int, vector<int>> m;

void dfs(int a) {
	if (!m.count(a)) {
		isvisit[a] = true;
		cout << a << " ";
		return;
	}
	vector<int> v = m[a];
	isvisit[a] = true;
	for (int i = 0; i < v.size(); i++) {
		if(!isvisit[v[i]]) dfs(v[i]);
	}
	cout << a << " ";
	return;
}

int main() {
	int n, t;
	cin >> n >> t;
	for (int i = 0; i < t; i++) {
		int a, b;
		cin >> a >> b;
		m[b].push_back(a);
	}
	
	for (int i = 1; i <= n; i++) {
		if(!isvisit[i]) dfs(i);
	}
}

 

<오늘의 TMI>
오랜만에 골드 문제를 푸는데 생각했던 것보다 훨씬 빠르게 끝나서 당황했다.
궁금해서 알고리즘 분류를 보니 위상 정렬로 푸는 문제인 듯 하다.
골드 3의 난이도로 느껴지지는 않아서 생애 첫 의견 제시를 해보았다 !