1766번

1766번 - 문제집

위상정렬과 우선순위큐를 이용한 문제였다.

나는 우선 순위 큐를 몰라서 따로 구글에서 검색해서 알아봤다. 

가장 핵심은 디폴트 값이 가장 큰 값을 가장 우선 순위로 두는 max heap 이라는 점이었다.

사실 이 문제는 가장 작은 값을 우선 순위로 둬야하는데, 그 테크닉을 -1을 곱해주는 방법을 통해서 극복했다.(물론 다른 분들꺼 답습)

##문제 풀면서의 고민##

우선 순위큐를 이용하면 중간에 정점들이 뒤섞여서 순서가 바뀌지 않을까? 하는 걱정이었다.

백준 SLACK 을 통해서 질문을 하니 갓분들께서 답변을 주셨다.

큐 안에 들어있는 값들은 indegree 값이 0이기 때문에 언제 빼내도 상관없고, 그렇기 때문에 섞을 수 있다고 했다.

나는 indegree 가 0이어도 뭔가 섞이지 않을까 머리가 속 시원하지는 않았다. 그런데 여러 위상 정렬 예시를 보면서 내가 가진 의문을 보니

약간은 의문이 풀리면서, 이해가 가는 것 같다. (사실 아직 뻥 뚤린 느낌은 아닌데..여러 사례에서 유추해보니 그렇다)

indegree 가 0이라는 것은 결국 어느 노드한테도 영향을 받지 않는 다는 뜻이니까....아무튼

위상 정렬 문제랑 똑같은 우선 순위 큐만 쓰면 되는 문제였다.

<정답 코드>

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N, M;
int indegree[32001];
vector<vector<int>> v;
int main()
{
    cin >> N >> M;
    
    v.resize(N + 1);
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        indegree[b]++;
    }
 
    priority_queue<int> pq;
 
    for (int i = 1; i <= N; i++)
    {
        if (indegree[i] == 0)
        {
            pq.push(-i);
        }
    }
 
    while (!pq.empty())
    {
        int now = -pq.top();
        pq.pop();
        printf("%d ", now);
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i];
            indegree[next]--;
 
            if (indegree[next] == 0)
            {
                pq.push(-next);
            }
        }
    }
 
 
    return 0;
}