[백준] 1766번 문제집

문제: 1766번: 문제집

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

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

	int n, m; // n: 문제의 수, m: 정보의 개수
	cin >> n >> m;

	vector<vector<int>> linkedList(n + 1); // 문제 번호는 1부터 시작하니까 인덱스 계산 편하돌록..
	vector<int> indegs(n + 1); // 진입차수 저장

	// 우선 순서 입력받기
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b; // a 문제를 b 보다 우선으로 풀어야함

		linkedList[a].push_back(b);
		indegs[b]++; // 진입차수 증가
	}
	
	priority_queue<int, vector<int>, greater<int>> noIndegNodes;
	for (int i = 1; i < n + 1; i++) {
		if (indegs[i] == 0)
			noIndegNodes.push(i); // 맨 처음 진입 차수가 없는 노드 번호 넣기
	}

	while (!noIndegNodes.empty()) {
		int node = noIndegNodes.top();
		noIndegNodes.pop();

		cout << node << " "; // 문제 번호 출력

		// 해당 문제와 연결되어 있는 문제들의 진입차수 조정해주기
		for (int next : linkedList[node]) {
			indegs[next]--; // 진입차수 -1 해주기

			// 그 결과 이웃 노드의 진입차수가 0이 되면 큐에 새로 넣어주기
			if (indegs[next] == 0)
				noIndegNodes.push(next);
		}
	}


	return 0;
}

 

그냥 전형적인 위상정렬 문제인데 우선 순위 큐를 곁들여서 풀면 아주 쉽게 해결되는 문제였다.

 

문제의 핵심은 일단 문제들 사이의 먼저 풀면 좋은 우선 순위가 주어져있는데, 이 우선 순위를 따르면서도 근본적으로는 쉬운 문제부터 해결한다는 것이다.

 

우선 순위 조건만 있었다면 그냥 위상정렬 풀이법을 그대로 가져다 풀어도 되지만 쉬운 문제부터 해결한다는 조건이 추가되어 있어서 추가적인 로직이 필요했다.

 

근데 사실 로직이랄 것도 없이 그냥 우선 순위 큐에 진입 차수가 없는 정점들을 넣고 빼면서 해결하면 돼서 아주 간단한 문제였다. 사실 이 문제가 왜 골드 2나 되는지 모르겠지만 그래도 좋았다ㅎ_ㅎ

 

이제 위상 정렬도 기본 정도는 쉽게 할 수 있게 된 것 같다. 어제 푼 문제처럼 응용으로 들어가면 머리가 나빠서 좀 오래걸리긴 하지만.. 열심히 하다보면 괜찮아지겠지

 

아 그리고 이건 사담이지만 오늘부로 백준 스트릭이 30일이 되었다. 중간 고사가 끝난지 벌써 한 달이 넘었다는 게 실감이 나고 한 달 동안 열심히 문제 풀었다는게 느껴져서 스스로 뿌듯했다. 알고리즘 기말 시험은 중간 보다 잘 봤으면 좋겠다.