백준 2252번: 줄 세우기 (C++)

문제링크

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

풀이방법

해당 문제는 기본적으로 위상 정렬 알고리즘을 이용하여 쉽게 해결하였다. 학생 A가 학생 B앞의 서야 한다는 것은 A노드가 B노드를 가르키고 있다고 생각하여 그림을 그려보면 쉽게 이해가 갈 것이다. 그렇게 그린 그래프를 바탕으로 위상 정렬 알고리즘을 구현하면 된다.

위상 정렬 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자

https://www.youtube.com/watch?v=Th-gLZUrd04&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=27

해답 코드는 다음과 같다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[32005];
int deg[32005];
int n,m,u,v;

queue<int> q;
vector<int> result;

int main()
{ 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	
	while (m--)
	{
		cin >> u >> v;
		adj[u].push_back(v);
		++deg[v];
	}

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

	while (!q.empty())
	{
		int cur = q.front(); q.pop();
		result.push_back(cur);
		for (auto nxt : adj[cur])
		{
			deg[nxt]--;
			if (deg[nxt] == 0) q.push(nxt);
		}
	}

	for (auto c : result) cout << c << ' ';
	
}