[백준 / BOJ] C++ 1766 문제집

1766번: 문제집

 

문제

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

1766번: 문제집

 

 

풀이

여러 가지 순서를 모두 만족하며 정렬해야 하므로 위상정렬 알고리즘을 사용한다. 기본적인 위상정렬 알고리즘에 추가적인 정렬 기준이 추가된 문제다. 기본적으로 일반적인 위상정렬과 같이 indegree 배열의 값이 0인 것들을 큐에 넣는데, 가능한 쉬운(번호가 작은) 문제부터 풀어야 하므로 큐 대신 최소 힙을 사용한다. STL에서 우선순위 큐는 최대 힙이므로 수를 넣고 뺄 때 (-) 부호를 붙여 최소 힙으로 사용해 준다.

 

각 순서를 입력받을 때마다 u -> v 간선을 추가하고 뒤의 인덱스의 indegree 배열의 값을 1 증가시킨다. indegree 배열의 값이 0인 정점을 모두 우선순위 큐에 추가하고 차례대로 top 원소에 대해 탐색한다. top 원소를 ans 배열에 추가하고 top에서 향하는 정점들에 대해 indegree 값을 1 감소시키고 0이 되면 우선순위 큐에 push 해 준다. 위 과정이 끝난 뒤 ans 배열의 값을 모두 출력한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M;
  vector<int> edge[32001], inDegree(32001, 0), ans;
  cin >> N >> M;
  while (M--) {
    int u, v;
    cin >> u >> v;
    inDegree[v]++;
    edge[u].push_back(v);
  }
  priority_queue<int> pq;
  for (int i = 1; i <= N; i++)
    if (inDegree[i] == 0)
      pq.push(-i);
  for (int i = 1; i <= N; i++) {
    int node = -pq.top();
    pq.pop();
    ans.push_back(node);
    for (int next : edge[node])
      if (--inDegree[next] == 0)
        pq.push(-next);
  }
  for (int e : ans)
    cout << e << ' ';
  return 0;
}