백준 1766번 문제집 - C++(cpp) 풀이

---

 

1. 각 문제를 그래프의 정점으로 생각한다.
2. A번 문제를 B번 문제보다 먼저 푸는 것이 좋다면 A에서 B로 가는 방향 간선을 추가한다.
3. 우선순위 큐를 가지고 위상 정렬한다.

 

1. 각 문제를 그래프의 정점으로 생각한다.

 선행 관계가 주어진 작업들의 작업 순서를 결정하는 것은 위상 정렬로 풀 수 있다. 먼저 주어진 상황을 그래프로 변환해야 한다. 각 문제를 정점으로 생각해준다.

 

2. A번 문제를 B번 문제보다 먼저 푸는 것이 좋다면 A에서 B로 가는 방향 간선을 추가한다.

 그리고 A가 B보다 선행되어야 한다면, A에서 B로 가는 방향 간선을 추가한다.

 

3. 우선순위 큐를 가지고 위상 정렬한다.

 완성된 그래프를 가지고 위상 정렬을 수행한다. 그런데 "가능하면 쉬운 문제부터 풀어야 한다."는 조건을 만족하기 위해서는, 만약 풀 수 있는 문제가 여러 개라면(큐에 들어있는 정점이 여러 개라면), 더 작은 번호를 가진 정점부터 방문해야 한다. 따라서 단순 큐가 아니라 작은 수부터 차례로 뱉어내는 우선순위 큐를 사용하여 위상 정렬을 수행해야 한다.

반응형

---

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N, M;
int indegree[32001];
vector<int> adjacents[32001];
priority_queue<int, vector<int>, greater<int>> pq;

void topology_sort() {
    for (int i = 1; i <= N; i++) {
        if (indegree[i] == 0) {
            pq.push(i);
        }
    }
    
    while (!pq.empty()) {
        int curr = pq.top(); pq.pop();
        
        cout << curr << " ";
        
        for (int i = 0; i < adjacents[curr].size(); i++) {
            int adj = adjacents[curr][i];
            indegree[adj]--;
            if (indegree[adj] == 0) {
                pq.push(adj);
            }
        }
    }
}

int main()
{
    cin >> N >> M;
    
    int s, e;
    
    for (int i = 0; i < M; i++) {
        cin >> s >> e;
        adjacents[s].push_back(e);
        indegree[e]++;
    }
    
    topology_sort();

    return 0;
}