백준 - 14567번 선수과목 (Prerequisite) (C++)

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

14567번: 선수과목 (Prerequisite)

 이번 문제는 과목간의 순서가 주어졌을 때, 각 과목들을 몇 번째 순서에 들을 수 있는지를 출력하는 문제이다. 과목(노드)들간의 순서가 주어지고, 이것들의 순서를 구하는 문제이다. 그렇기에 순서가 정해져 있는 노드들의 순서를 결정하기 위한 위상 정렬 알고리즘을 이용하면 쉽게 풀 수 있는 문제이다. 그런데 이 문제는 단순히 과목들을 순서대로 출력하는 것이 아닌, 과목들의 순번을 출력하는 문제이다. 그렇기 때문에 정렬하는 도중에 과목의 순서 역시 같이 기억하고 있어야 한다. 그리고 이는 코드 속 queue<pair<int, int>> q 라는 큐에서 pair의 두 번째에 저장하여 진행하였다.

 

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <deque>
#include <cmath>
#include <stack>
#include <cstring>
#include <typeinfo>
#include <iomanip>
#include <limits.h> 
#include <map>
#pragma warning(disable:4996)

using namespace std;

#define MAX 1001

int N, M;
int inDegree[MAX];
vector<int> links[MAX];
int answer[MAX];

void Check()
{
	queue<pair<int, int>> q;
	
	for (int node = 1; node <= N; ++node)
	{
		if (inDegree[node] == 0)
			q.push({ node, 1 });
	}

	while(!q.empty())
	{
		int curNode = q.front().first;
		int curTime = q.front().second;
		q.pop();

		answer[curNode] = curTime;

		for (int i = 0; i < links[curNode].size(); ++i)
		{
			int nxtNode = links[curNode][i];

			--inDegree[nxtNode];

			if (inDegree[nxtNode] == 0)
				q.push({ nxtNode, curTime + 1 });
		}
	}
}


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

	cin >> N >> M;

	for (int i = 0; i < M; ++i)
	{
		int a, b;
		cin >> a >> b;

		links[a].push_back(b);
		inDegree[b]++;
	}

	Check();

	for (int node = 1; node <= N; ++node)
		cout << answer[node] << " ";


	return 0;
}