BOJ - 2252 줄 세우기

2252번 줄 세우기

학생들을 키 순서대로 줄을 세우려 하는데, 키의 정보는 두 학생을 비교하여 누가 더큰지만 알 수 있다.

위 상황에서 학생들을 키순으로 줄을 세우는 문제이다.

문제 해결 전략

키 순서를 유지한 채로 모든 학생들을 줄을 세워야 하기 때문에 위상정렬을 활용하여 문제를 해결할 수 있다.

학생들의 키 비교가 주어지면 앞에 서야 하는 학생에서 뒤에 서야하는 학생으로 방향을 가진 그래프를 생성한다.

그래프를 생성하면서 뒤에 선 학생 기준으로 모든 학생 중 그 학생 앞에 서야 하는 학생 수 를 저장한다.

그리고 현재 탐색 대상이 된 노드에 대하여 뒤에 서야 하는 학생 중 앞에 서는 학생이 없는 경우 큐에 삽입하며 모든 노드에 대해 과정을 반복한다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m;
vector<int> v[32001];
int arr[32001];
queue<int> q;
void sol(){
    while(!q.empty()){
        int x = q.front();
        q.pop();

        cout << x << " ";

        for(int i=0;i<v[x].size();i++){
            arr[v[x][i]]--;
            if(arr[v[x][i]] == 0)
                q.push(v[x][i]);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        arr[b]++;
    }

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

출처 : https://www.acmicpc.net/problem/2252