[C++] 백준 2252: 줄 세우기

문제 이해

- N명의 학생들을 키 순서대로 줄을 세우려고 한다.

- 단 키를 각각 재는 것이 아닌 비교하여 순서를 정한다.

- M: 키를 비교한 횟수 (1 ~ 100,000, 10^5)

- N: 학생 수 (1 ~ 32,000, 10^4)

- 답이 여러가지일 경우 아무거나 출력한다.

 

 

문제 풀이

학생들의 키의 순서를 비교한 값이 나와있는 이 문제는

특정 조합의 순서가 정해져 있는 그래프의 전체 순서를 결정하는 문제이다.

 

즉, 위상 정렬을 사용하면 쉽게 풀 수 있는 문제이다.

 

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<int> v[32005];
int inDegree[32005];
queue<int> q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin>>a>>b;
        v[a].push_back(b);
        inDegree[b]++;
    }

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

    while(!q.empty()){
        int now = q.front();
        q.pop();
        cout<<now<<" ";

        int size = v[now].size();
        for(int i = 0; i < size; i++){
            int next = v[now][i];
            inDegree[next]--;

            if(inDegree[next] == 0){
                q.push(next);
            }
        }
    }
    
    return 0;
}

 

위상 정렬 문제의 제일 기본형으로 볼 수 있는 문제였다!