[C++] 1766번 문제집 - 자료 구조, 그래프 이론, 우선순위 큐, 위상 정렬

1. 문제

• 난이도 순서로 된 1~N번까지 총 N개의 문제로 되어 있는 문제를 풀려고 한다. 민오는 세 가지 조건에 따라 문제를 풀 순서를 정한다.
  1. N개의 문제를 모두 풀어야 한다.
  2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
  3. 가능하면 쉬운 문제부터 푼다.
• 문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건에 맞는 민오가 풀 문제의 순서를 결정하시오.

<입력>

• - 1 -   문제의 수 \(N(1 \leq N \leq 32,000)\), 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 \(M(1 \leq M \leq 100,000)\)
• - M개의 줄 -   두 정수의 순서쌍 A, B. A번 문제가 B번 문제보다 먼저 푸는 것이 좋다.
• 항상 문제를 모두 풀 수 있는 경우만 주어진다.

<출력>

• - 1 -   민오가 풀어야 하는 순서 출력

2. 재정의

• 가능하면 쉬운 문제를, 항상 먼저 푸는 것이 좋은 문제를 먼저 풀 때 문제 푸는 순서를 결정하시오.

3. 해결 방법

• 위상 정렬로 풀되 queue를 문제 번호에 따른 priority_queue로 바꿔서 푼다.

4. 실수한 점, 개선할 점

• X

 

<코드>

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

using namespace std;

const int MAX_N = 32001;

// <문제>
// 문제의 수 N, 먼저 푸는 것이 좋은 문제에 대한 정보의 수 M
int N, M;
// 문제 푸는 조건 용 단방향 그래프 adj
vector<int> adj[MAX_N];

// topology Sort
// 진입차수가 0인 문제 중 쉬운 문제 순으로 정렬된 우선순위 큐
priority_queue<int, vector<int>, greater<int>> pq;
// 진입차수 inDegree
int inDegree[MAX_N];
// 위상정렬 결과
vector<int> result;

void input() {
    cin >> N >> M;
    for(int i=0; i<M; i++) {
        int A, B;
        cin >> A >> B;
        adj[A].push_back(B);
        // 진입차수 설정하기
        inDegree[B]++;
    }
}

void topologySort() {
    for(int i=1; i<=N; i++) {
        // 진입차수가 0인 노드를 우선순위 큐에 저장
        // 쉬운 문제부터 들어감
        if(!inDegree[i])
            pq.push(i);
    }
    
    // N번 정렬하면 위상 정렬이 끝
    for(int i=0; i<N; i++) {
        int x = pq.top();
        pq.pop();
        
        result.push_back(x);
        for(auto next : adj[x]) {
            // 연결된 노드의 진입차수가 0일 경우 우선순위 큐에 저장
            if(!(--inDegree[next]))
                pq.push(next);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    topologySort();
    
    for(int i=0; i<N; i++)
        cout << result[i] << ' ';
    
    return 0;
}

 

<위상 정렬>

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

25. 위상 정렬(Topology Sort)

 

<priority queue>

https://kbj96.tistory.com/15

[C++ STL] Priority_queue 사용법

 

<문제 바로가기>

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

1766번: 문제집

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.