[C++] 문제집 (1766번) 위상 정렬

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

1766번: 문제집

---

문제풀이

위상정렬 문제 접근 방법을 기억하지 못해 정답을 참고했다. 이참에 위상정렬에 대해 다시 한번 공부해 보았다.

위상 정렬은 "사이클이 없는 다이렉션 그래프" 문제를 풀 때 사용한다. 즉 순서가 정해져 있고, 이 순서가 순환하지 않아야 한다.

위상정렬은 위와 같은 조건을 가진 그래프를 "진입차수"의 개수를 이용하여 순서대로 출력하도록 또는 동작하도록 할 수 있다.

이 문제를 예로들어보면, 예제에서 4번을 2번보다 먼저, 3번을 1번보다 먼저 풀어야 된다는 조건이 있다. 그럼 그래프는 다음과 같이 그릴 수 있다.

4 -> 2

3 -> 1

4번을 풀어야 2번을 풀 수 있고, 3번을 풀어야 1번을 풀 수 있기 때문에 순서대로 그래프를 그린것이다.

그럼 이제 각 번호의 진입 차수는 1부터 순서대로 1 1 0 0이 된다. 문제의 조건에 순서가 없을경우 "작은 숫자"의 문제 먼저 풀도록 했으니 우선순위 큐에 "진입 차수가 없는" 문제 번호를 넣는다.

 

그리고 큐의 값을 하나씩 빼며 출력을 하고, 뺀 값이 또 다음 어떤것과 연결되어 있다면 해당 값의 "진입차수"를 1 감소시켜 준뒤 0이된다면 큐에 넣는 동작을 반복하면 된다.

이 때 4 -> 2, 4->1 과 같이 여러 개가 등록될수 있으므로 배열은 vector를 사용하여 2차원으로 만들고, 진입차수를 저장하는 배열은 1차원 배열로 만든다.

 

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

using namespace std;

// 그래프
vector<int> arr[32001];
// 진입 차수
int in[32001];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    for(int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        arr[a].push_back(b);
        in[b]++;
    }

    priority_queue<int, vector<int>, greater<int>> pq;
    // 진입차수가 0이면 우선순위 큐에 넣는다.
    for(int i=1; i<=n; i++) {
        if(in[i] == 0) pq.push(i);
    }

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

        cout << idx << " ";

        // 뺀 값에 연결되어 있는 값이 있다면 진입 차수를 1감소시켜주고, 진입 차수가 0이 된다면 큐에 넣어준다.
        for(int i=0; i<arr[idx].size(); i++) {
            in[arr[idx][i]]--;
            if(in[arr[idx][i]] == 0) pq.push(arr[idx][i]);
        }
    }

    return 0;
}

 

참고

https://m.blog.naver.com/ndb796/221236874984

https://yabmoons.tistory.com/411