BOJ 1766번: 문제집

문제

문제 바로가기> BOJ 1766번: 문제집

1766번: 문제집

 

풀이

세가지 조건에 따라 문제를 풀 순서를 출력해야한다.

 

1. N개의 문제는 모두 풀어야 한다.

    ⇒ 항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다고 했으니, 신경 쓸 필요 없다.

 

2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.

    ⇒ 위상 정렬을 이용해서, 정해진 순서를 만족시키도록 한다.

 

3. 가능하면 쉬운 문제부터 풀어야 한다.

    ⇒ PriorityQueue를 이용한다.

        (min heap)으로 만들어서 조건을 만족하는 경우(진입 차수가 0인 경우),

        쉬운 문제부터 풀도록 한다.

 

#include<iostream>
#include<vector>
#include<queue>
#define MAX 32001
using namespace std;

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

void input() {
	cin >> N >> M;
	
	int a, b;
	while (M--) {
		cin >> a >> b;
		order[a].push_back(b);
		inDegree[b]++;
	}
}

void solution() { // 먼저 푸는 것이 좋은 경우 반드시 먼저 품, 가능한 쉬운 문제 부터
	priority_queue<int> pq;
	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0) pq.push(-i); // min heap
	}

	while (!pq.empty())
	{
		int num = -pq.top(); 
		cout << num << " ";
		pq.pop();

		for (int i = 0; i < order[num].size(); i++) {
			if (--inDegree[order[num][i]] == 0) pq.push(-order[num][i]);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	solution();
}