[백준] 1766번 문제집 C++ 문제풀이

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

1766번: 문제집

문제 풀이

전형적인 위상정렬 문제다.

위상정렬이란 순서가 정해져있는 작업을 차례로 수행할 때, 순서를 결정하는 알고리즘이다.

여기서는 고려해야하는 순서는 2가지였다.

첫 번째는 '먼저 푸는 것이 좋은 문제'의 경우에는 먼저 풀어야한다.

두 번째는 문제집 번호가 낮은 번호부터 큰 번호 순서로 진행되어야 한다.

이 두가지를 고려해 queue에 진입차수가 0인 문제가 하나만 들어있게 만들어, 위의 순서들을 고려해 문제를 해결했다.

문제 시간이 오래걸려, 다른 분들의 풀이를 찾아보니 Priority Queue를 이용해 문제를 해결하셨던데, 아직 많이 사용해보지 않아 어색해서 나는 기존의 풀이를 올린다.

위의 경우가 pq를 이용한 경우, 아래의 경우가 내 풀이

소스 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int indegree[32001] = { 0 };
vector<int> problem[32001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int fir, sec;
		cin >> fir >> sec;
		problem[fir].push_back(sec);
		indegree[sec] += 1;
	}

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

	int cnt = 0;
	while (cnt < n) {
		int idx = q.front();
		indegree[idx] = -1; // 방문했음을 표시
		cout << idx << " ";
		q.pop();
		cnt += 1;
	
		for (int i = 0; i < problem[idx].size(); i++) {
			int y = problem[idx][i];
			indegree[y] -= 1;
		}

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

	return 0;
}