백준 1766 문제집

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

 

 

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

using namespace std;

int inDegree[32001];
bool visit[32001];

vector<int> g[32001];


vector<int> ans;

int main() {


    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n, m;

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;

        cin >> u >> v;

        g[u].push_back(v);
        inDegree[v]++;

    }


    priority_queue<int, vector<int>, greater<int>> q;

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

    while (true) {

        if(q.empty()) {
            break;
        }

        int cur = q.top();
        q.pop();
        ans.push_back(cur);

        for (int i = 0; i < g[cur].size(); i++) {
            inDegree[g[cur][i]]--;
            if (!inDegree[g[cur][i]] && find(ans.begin(), ans.end(), g[cur][i]) == ans.end()) {
                q.push(g[cur][i]);
            }
        }

        g[cur].clear();
    }


    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }




    return 0;
}

 

  위상 정렬 문제이다.

 다만 기본적인 위상 정렬과는 살짝 다르다. 이 문제의 3번 조건 때문이다. 

 

          3. 가능하면 쉬운 문제부터 풀어야 한다.

  

 이 조건에 의해 문제를 풀 때는 가능한 문제 중 가장 작은 숫자의 문제부터 풀어야 한다. 이를 해결하기 위해 우선순위 큐를 사용하였다.

 

 풀이

        g[u].push_back(v);
        inDegree[v]++;

 

 문제의 순서를 입력받을 때 그래프에 해당 노드를 넣고, inDegree(해당 버텍스를 가리키는 버텍스의 수)를 계산해준다.

 

    priority_queue<int, vector<int>, greater<int>> q;

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

 

 inDegree가 없는 문제는 순서에 구애를 받지 않으므로 큐에 집어넣어 준다. 우선순위 큐에 넣으므로 가장 쉬운 문제부터 연산을 진행하게 된다.

    while (true) {

        if(q.empty()) {
            break;
        }

        int cur = q.top();
        q.pop();
        ans.push_back(cur);

        for (int i = 0; i < g[cur].size(); i++) {
            inDegree[g[cur][i]]--;
            if (!inDegree[g[cur][i]] && find(ans.begin(), ans.end(), g[cur][i]) == ans.end()) {
                q.push(g[cur][i]);
            }
        }

        g[cur].clear();
    }

 이후, 해당 문제를 풀면서 이를 정답 벡터에 넣고, 이를 빼면서 해당 문제 다음 풀 수 있는 문제들의 inDegree를 계산해준다. 연산 후 inDegree가 없게 되면 이제 해당 문제(g[cur][i])를 풀 자격이 생기므로 큐에 집어넣는다. 

 모든 연산 종료 후 정답 벡터를 순서대로 출력하면 답이 된다.