[Algorithm] 2252: 줄 세우기

📦2252: 줄 세우기

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-18
문제 확인하기

풀이

• 위상정렬 문제이다.
• Workbook-1766 문제와 동일하지만 조건이 적어 더 쉬운 문제이다.
• 순서를 지켜 줄을 세우면 되기 때문에 먼저 줄을 서야 하는 친구보다 나중에 서야 하는 친구는 +1을 통해서 순서를 뒤로 미룬다.

#include <iostream>
#include <queue>
#define endl '\n'
using namespace std;
 
int N, M, A, B;
int degree[32002];
vector<int> after[32002];
queue<int> q;
 
void Input(){
    cin >> N >> M;
    for(int i=0; i<M; i++){
        cin >> A >> B;
        after[A].push_back(B);
        degree[B]++;
    }
}
 
void Solution(){
    for(int i=1; i<=N; i++){
        if(degree[i] == 0) q.push(i);
    }
 
    for(int i=1; i<=N; i++){
        int cur = q.front(); q.pop();
 
        cout << cur << ' ';
 
        for(auto nxt : after[cur]){
            degree[nxt]--;
            if(degree[nxt] == 0) q.push(nxt);
        }
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Solution();
 
    return 0;
}