[백준/Baekjoon] 1766 문제집 C++ :: Topological sort

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

1766번: 문제집

---

1. Logic

2252번 문제와 동일하게 위상정렬로 푸는 문제지만 살짝 다르다. 1766번 문제집은 문제를 푸는 조건이 있다.

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

이중 키포인트는 3번이다. 나는 위상정렬을  BFS를 활용하여 푸는데 1부터 n까지 queue에 넣을 때 순서대로 넣기 때문에 그냥 넣으면 queue에 들어온 순서대로 정렬하기 때문에 해당 문제에서는 쉬운문제부터 풀 수 없다. 그렇기 때문에 queue대신 priority_queue를 사용하여 풀이해 주었다. 

우선순위 큐에 값을 넣을 때 -를 붙여 오름차순으로 정리해주었다. 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

vector<int> graph[32001];
int inDegree[32001];

int n, m;

void topologicalSort() {
    priority_queue<int> pq;

    for(int i = 1; i <= n; i++) {
        if(!inDegree[i])
            pq.push(-i);
    }

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

        cout << cur << " ";

        for(int i = 0; i < graph[cur].size(); i++) {
            inDegree[graph[cur][i]]--;
            if(!inDegree[graph[cur][i]])
                pq.push(-graph[cur][i]);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        graph[a].push_back(b);
        inDegree[b]++;
    }

    topologicalSort();
}

 

 

---

3. Feedback

위상정렬을 공부하고 이후 비슷한 문제를 찾았다. 문제를 보자마자 위상정렬에 우선순위큐를 사용하면 풀릴것 같아서 시도했고, 위상정렬 알고리즘도 템플릿을 보지 않고 생각해서 풀었는데 수월하게 맞아서 뿌듯했다.

 

순서를 따지는 문제는 자료구조를 어떻게 사용할지 생각해 보는것 또한 좋은 접근방법인 것 같다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90