[백준][C++] 1766번: 문제집

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

1766번: 문제집

 

문제를 푸는 순서에 대한 조건이 주어지고 문제를 푸는 순서를 출력하는 문제이다.

 

문제를 푸는 순서가 조건으로 '정해져 있기'때문에

'순서가 정해져 있는 작업'을 차례로 수행해야 할 때 그 순서를 결정하기 위해 사용하는 위상 정렬을 사용하여 풀어보았다.

 

https://blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

위상 정렬은 위 블로그를 보고 공부했다.

 

위상 정렬을 안다면 비교적 쉽게 풀 수 있는 문제였다.

항상 풀 수 있는 경우만 준다 했으므로 사이클의 여부는 고려하지 않았다.

먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 하므로 진입 차수가 0인 노드만 큐에 삽입했다. 진입 차수가 0이어야 먼저 풀어야 하는 문제가 없으므로.

그리고 가능하면 쉬운 문제부터 풀어야 한다 했으므로 큐에 삽입한 노드들이 오름차순으로 정렬되어야 난이도가 낮은 문제부터 꺼낼 수 있기에 우선순위 큐를 사용해 오름차순으로 정렬해주었다.

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 32001

using namespace std;

vector<int> a[MAX];
int N, inDegree[MAX], result[MAX];

void solve() {
	priority_queue<int, vector<int>, greater<int>> q;
	
	for(int i=1; i<=N; i++) {
		if(inDegree[i] == 0) q.push(i);
	}
	
	for(int i=1; i<=N; i++) {
		int x = q.top();
		q.pop();
		result[i] = x;
		
		for(int i=0; i<a[x].size(); i++) {
			int y = a[x][i];
			if(--inDegree[y] == 0) {
				q.push(y);
			}
		} 
	}
}

int main(void) {
	int M;
	cin >> N >> M;
	
	int s, e;
	// 그래프, 진입 차수 
	for(int i=0; i<M; i++) {
		cin >> s >> e;
		a[s].push_back(e);
		inDegree[e]++;	
	}
	solve();
	
	for(int i=1; i<=N; i++) {
		cout << result[i] << " ";
	}
}

 

 

항상 풀 수 있는 경우만 준다 했으므로 모든 노드를 다 돌 필요없이 큐가 빌 때까지 반복문을 돌려줘도 된다.