백준(BOJ) 1766 : 문제집

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

1766번: 문제집

 

 

작업들의 순서가 주어지고 후에 이루어지는 작업들은 앞에 이루어지는 작업들이 모두 완료되어야만 가능한 문제들은

위상 정렬(topological sort) 로 해결할 수 있다.

이 문제 또한 단순한 위상 정렬 문제로 보이지만 3번 조건을 보면 가능한 쉬운 문제부터 풀어야한다. 라고 명시되어있다.

문제의 난이도는 문제의 번호이므로 수행할 수 있는 문제 중 가장 낮은 번호의 문제를 출력하면 되는 것이다.

queue를 이용한 위상 정렬을 할 때에 수행이 가능한 작업들은 queue에 담기게 되므로 queue에 있는 원소들 중 가장 작은 것부터 해결을 하면 될 것이다. 위와 같은 상황에 딱 맞는 자료구조가 존재하는데 바로 우선순위 큐(힙)이다.

queue대신에 최소 힙을 이용하여 위상 정렬을 하도록 하자!

 

아래는 소스코드이다.

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 987654321;

vector<vector<int> >adj(32001);
int degree[32001] = {};

int N, M ;

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  cin >> N >> M;
  for(int i = 0 ; i < M ; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].pb(b);
    degree[b]++;
  }

  priority_queue<int, vector<int>, greater<int> > pq;

  for(int i = 1 ; i <= N ; i++) {
    if(degree[i] == 0) pq.push(i);
  }
  vector<int> ans;
  for(int i = 0 ; i < N ; i++) {
    int cur = pq.top();
    ans.pb(cur);
    pq.pop();
    for(int j = 0 ; j < adj[cur].size() ; j++) {
      int nxt = adj[cur][j];
      degree[nxt]--;
      if(degree[nxt] == 0) pq.push(nxt);
    }
  }
  for(auto x : ans) {
    cout << x << ' ';
  }
  cout << endl;
}