1766 문제집

1766. 문제집 / c++ / Gold2 / 1시간 +

문제

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

1. 문제 N개, 선행 문제 M개
2. 문제는 숫자가 클 수록 어려운 문제
3. 선행문제는 반드시 먼저 풀어야 한다.
4. N개의 문제를 다 풀었을 때 그 순서는?

접근 방식

자료구조, 우선순위 큐, 위상정렬

1. 연결 리스트로 풀어보려고 직접 연결 리스트를 만들었다. (시간초과)
2. 아무리 생각해보 모르겠어서, 문제 분류를 봤다. 우선순위 큐와 위상 정렬이 적혀있었다.
3. 구글에 위상 정렬을 찾아봤다.
4. 위상 정렬대로 풀어봤다. (해결)

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <queue>
using namespace std;

vector<int> adjVec[32'001] = {};
int degreeArr[32'001] = {};
int order[32'001] = {};
int N, M, fromNum ,toNum;

priority_queue<int, vector<int>, greater<int>> q;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;

	while (M-- > 0)
	{
		cin >> fromNum >> toNum;
		adjVec[fromNum].push_back(toNum);
		degreeArr[toNum]++;
	}

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

	for (int i = 1; i <= N; ++i)
	{
		int now = q.top(); q.pop();
		order[i] = now;
		for (int j = 0; j < adjVec[now].size(); ++j)
		{
			int next = adjVec[now][j];
			if (--degreeArr[next] == 0)
			{
				q.push(next);
			}
		}
	}

	for (int i = 1; i <= N; ++i)
	{
		cout << order[i] << ' ';
	}
	cout << '\n';

	return 0;
}

다시 생각해 볼 점

1. 위상 정렬을 알게 되었다.
2. 내가 본 글에서 위상정렬은 그냥 큐를 사용했었는데, 문제에서는 기본적으로 낮은 번호의 문제를 더 빨리 풀도록 되어 있어서 우선순위 큐를 사용했다.