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


풀어야할 문제들이 난이도로 주어진다. 또한 어떤 문제를 어떤 문제보다 먼저 풀어야한다는 식의 데이터가 주어지므로, 위상 정렬을 활용한다.


다만 큐에서 꺼낼때, 난이도가 낮은 문제를 먼저 꺼내야 하기 때문에, min heap을 사용해주면 된다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
 
int n, m, ind[32002];
vector<int> v[32002];
priority_queue<int, vector<int>, greater<int> > q;
void tpgSort() {
    for (int i = 1; i <= n; i++) { //indegree 0인거 큐에 넣고 시작
        if (ind[i] == 0) q.push(i);
    }
 
    for (int i = 0; i < n; i++) { // 노드의 개수보다 더 많이 돌면 사이클
        if (q.empty()) cout << "cycle occured\n";
 
        int cur = q.top(); q.pop();
        cout << cur << ' '; //노드 삭제
 
        
        for (int i = 0; i < v[cur].size(); i++) {
            ind[v[cur][i]]--; //삭제된 노드와 연결된 간선 제거
            if (ind[v[cur][i]] == 0) q.push(v[cur][i]);
        }
 
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
 
    while (m--) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        ind[b]++;
    }
    tpgSort();
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1516 게임 개발 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 1717 집합의 표현 C++  (0) 2019.08.14

+ Recent posts

티스토리툴바