백준 문제 1766번 문제집 문제풀이 c++

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

1766번: 문제집

 

문제해석

 

위상정렬 문제인데 저번에 풀었던 2252번 줄 세우기보다 조건이 많아졌다.

 

무엇보다 3번 조건때문에 이 문제를 dfs로 풀경우 제일 깊은 곳까지 들어가서 숫자를 확인해야한다.

당연히 이렇게 풀면 매우 비효율적이되기때문에 bfs 그리고 큐대신 우선순위 큐를 사용하여 풀어야 한다.

 

bfs 위상정렬에서는 indegree가 필요하기 때문에 indegree 배열을 최대 정점번호가 32000이므로 +1만큼 선언 해준다.

 

indegree[i] : 그래프를 그렸을때 i 정점을 가리키고있는 화살표의 개수 라고 보면 된다.

 

indegree가 0이란뜻은 나를 가리키는 화살표가 없기 때문에 시작 지점이 될 수 있다는 뜻이기 때문에 먼저 우선순위큐에 넣고 큐에 넣은 정점을 비우면서 해당 vertex와 edge를 전부 지우고 indegree를 업데이트 해주고 업데이트 된 indegree가 0이 되면 우선 순위 큐에 넣어주는것을 우선순위큐가 빌 때까지 한다.

 

4 2

4 2

3 1

입력이 위처럼 들어오면

초기 indegree 상태

[1] [2] [3] [4]

 1   1  0   0

 

indegree[3]과 indegree[4]가 0이므로 pq에 3 4를 넣고 pq.top() 3을 출력 후 지우면 3과 관련된 edge가 전부 지워지므로

indegree 상태가 아래 처럼 변한다.

[1] [2] [3] [4]

 0   1  0   0

 

indegree[1]이 0이 되었으므로 pq에 1을 넣으면 pq.top()은 1이 된다. 이를 출력 후 지운다 1과 관련한 edge는 없기때문에 indegree배열의 변화 역시 없다.

 

다음 pq.top()은 4가 되고 이를 출력 후 지우면 indegree 상태는

[1] [2] [3] [4]

 0   0  0   0

가 되고 indegree[2]이 0이 되었으므로 pq에 2를 넣고  pq.top()은 2 이를 출력 후 지우면 pq가 비기 때문에 끝이 난다.

 

지금까지 순서대로 3 1 4 2가 출력되었고 이게 답이된다.

 

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
priority_queue < int , vector<int> , greater<int> > pq;
int indegree[32001];
vector <int> v[32001];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,m; cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        indegree[b]++;
    }
    for(int i=1; i<=n; i++)
    {
        if(indegree[i]==0)
        {
            pq.push(i);
        }
    }
    while(!pq.empty())
    {
        int x=pq.top();
        pq.pop();
        for(int i=0; i<v[x].size(); i++)
        {
            indegree[v[x][i]]--;
            if(indegree[v[x][i]]==0)
            {
                pq.push(v[x][i]);
            }
        }
        cout<<x<<" ";
    }
}