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

문제 링크

1766번: 문제집

---

요즘 위상정렬에 관한 문제들을 풀고 있는데, 간단한 문제 하나를 소개해드리려고 합니다.

풀이

위상정렬 + 우선순위큐(최소힙)로 풀이하면 됩니다.

1. 일반적인 위상정렬(`indegree` 배열 활용)을 만듭니다.
2. 보통 위상정렬은 `queue` 를 사용하지만, 이 문제에서는 최소 힙 우선순위큐를 사용합니다.
   문제에서 주어진대로, "가능하면 쉬운 문제(1번부터)"와 "먼저 푸는 것이 좋은 문제"를 풀어야하기 때문에 최소 힙을 사용합니다.

풀이코드

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

#define endl "\n"

vector<int> graph[32001];
int deg[32001];

void solve() {
  int n, m;
  cin >> n >> m;
  while(m--) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
    deg[b]++;
  }

  priority_queue<int, vector<int>, greater<>> pq;
  for (int i = 1; i <= n; i++) {
    if (deg[i]) continue;
    pq.push(i);
  }

  while(!pq.empty()) {
    int cur = pq.top(); pq.pop();

    cout << cur << ' '; 
    for (auto e : graph[cur]) {
      deg[e]--;
      if (deg[e]) continue;
      pq.push(e);
    }
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

 

배운점

• 우선순위 큐를 활용한 위상정렬 코딩 방법을 알게 되었습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!