백준 1766번 [문제집](C++) -yes6686- 티스토리

백준 문제 풀이: 1766 [문제집]

---

문제 링크: https://www.acmicpc.net/problem/1766

문제 설명:

여러 개의 문제를 풀어야 하는 상황에서, 문제 간의 선행 관계가 주어집니다. 선행 관계를 만족시키면서 가능한 사전 순으로 문제를 풀어야 합니다. 각 문제 번호는 1부터 시작하며, 총 N개의 문제와 M개의 선행 관계가 주어집니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector v[32001];
int indegree[32001];
priority_queue<int, vector<int>, greater<int>> q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    int a, b;

    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        indegree[b]++;
    }

    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int current = q.top();
        q.pop();
        cout << current << ' ';
        for (int next : v[current]) {
            indegree[next]--;
            if (indegree[next] == 0) {
                q.push(next);
            }
        }
    }
}

예제

입력:
4 4
4 2
3 1
1 2
2 3

출력:
3 1 4 2

---

코드 설명

• 입력: 문제 개수(N)와 선행 관계(M)를 입력받고, 각 문제에 대한 간선 정보를 저장합니다.
• 위상 정렬:
  • 진입 차수가 0인 문제를 우선순위 큐에 삽입합니다.
  • 큐에서 문제를 하나씩 꺼내며 출력하고, 해당 문제와 연결된 문제들의 진입 차수를 감소시킵니다.
  • 감소된 진입 차수가 0이 되면 큐에 삽입합니다.
• 출력: 사전 순으로 풀 수 있는 문제 번호를 출력합니다.

시간 복잡도

• 간선 처리: O(M)
• 큐 연산: O(N log N), N은 문제 수
• 전체 시간 복잡도: O(N log N + M)

---

결과

위상 정렬을 이용해 선행 관계를 만족시키면서 가능한 사전 순으로 문제를 풀 수 있습니다. 큐를 이용하여 효율적인 처리가 가능합니다.