1766 - 문제집

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

처음에는 문제의 접근 방향을 후위순회처럼 생각했다. 어떤 x번째를 하기 위해서 그 이전것을 무조건 해결해야하는 방식.
틀리고 나서 문제를 다시 이해했는데, 깨달은 테스트 케이스부터 말하자면 아래와 같다.

5 3
4 1
2 3
5 3

내가 생각한 이 입력의 정답은

2 4 1 5 3

이다.

1번보다 4번을 먼저 풀어야하고, 3번보다 2, 5번을 먼저 풀어야한다. 1번을 풀기 위해서 4번을 풀어야하는데, 같은 우선순위에서 4번보다는 2번이 쉽다. (둘 다 1개의 문제 앞에 있음)
2번을 풀고 4번을 풀면, 1번이 풀리고 남은 5번을 풀면 3번이 풀린다.

처음에 생각한 대로라면 4 1 2 5 3 이 나와야하는데, 이게 틀려서 위 생각으로 다시 풀었더니 맞았다.
위상정렬 도중에 indegree가 없는 정점을 선택할때마다 번호가 작은(문제 난이도가 낮은) 정점을 선택하게 하면 된다.

#include <bits/stdc++.h>
using namespace std;

void topological(int vertex, int edges){
    vector<int> adj[vertex];
    vector<int> indegree(vertex, 0);
    while(edges--){
        int s, e;
        scanf("%d %d", &s, &e);
        adj[s-1].push_back(e-1);
        indegree[e-1] += 1;
    }
     
    priority_queue<int, vector<int>, greater<int>> q;
    for(int i=0; i<vertex; ++i){
        if(indegree[i] == 0){
            // 들어가는 간선이 없는 노드 (시작점)
            q.push(i);
        }
    }
     
    while(!q.empty()){
        int node = q.top();
        q.pop();
        printf("%d ", node+1);
        for(int i=0; i<adj[node].size(); ++i){
            int nextNode = adj[node][i];
            indegree[nextNode] -= 1;
            if(indegree[nextNode] == 0) q.push(nextNode);
        }
    }
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    topological(n, m);
    return 0;
}