[백준 1766] 문제집 (C++)

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

1766번: 문제집

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, A, B;
int inDegree[32001]; // 진입 차수 저장
vector<int> graph[32001]; // 간선 정보 저장
vector<int>result; 
priority_queue<int, vector<int>, greater<int>> pq; //위상 정렬을 위한 큐 (오름차순)

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;
    for(int i=0; i<M; i++) 
    {
        cin >> A >> B;
        graph[A].push_back(B);
        inDegree[B]++; //진입 차수 즈가 (A가 우선)
    }

    for(int i=1; i<=N; i++) if(inDegree[i]==0) pq.push(i);

    while(!pq.empty())
    {
        int cur = pq.top(); pq.pop();
        cout << cur << " ";
        for(int i=0; i<graph[cur].size(); i++) //인접 노드 체크
        {
            int next = graph[cur][i];
            if(--inDegree[next]==0) pq.push(next);
        }
    }


    return 0;
}

 

기본적인 위상정렬 문제에 오름차순 정렬이 추가된 문제다.

해당 문제의 3번 조건인 가능하면 쉬운 것 부터 풀어야 한다는 조건을 해결하기 위해 작은 값부터 먼저 해결해줘야 한다.

이를 위해 우선 순위 큐를 이용해 큐에 담긴 값을 오름차순으로 정렬해준다.

이외에는 기본적인 위상정렬 문제와 동일하다.

 

참고링크 : https://blob-thinking.tistory.com/281

[백준 2252번] 줄 세우기 (C++)