BOJ 2252번 줄세우기

BOJ : https://www.acmicpc.net/problem/2252

github : https://github.com/junho0956/Algorithm/blob/master/2252/2252/%EC%86%8C%EC%8A%A4.cpp

 

위상정렬 형태의 코드입니다.

 

v[a] 내부의 값들은 a 뒤에 와야하는 값들을 의미하는 것이고

in[b] 의 값들은 b 앞에 와야하는 값들의 갯수 입니다.

이 값들을 비교대로 나열했다고 생각해보면 반드시 가장 앞에 서야하는 값이 존재하게 됩니다.

그게 in[b] == 0 의 기준이 됩니다.

이 값들을 queue 에 넣어놓고, 현재 queue 내부의 값들에는 순서(서열)가 상관없으니

순서대로 뽑아서 자신의 뒤에 와야할 숫자들을 탐색합니다.

in[자신의 뒤에 올 숫자]를 비교할때마다 1씩 감소시키다가

in[자신의 뒤에 올 숫자]가 0이 된다면 더이상 그 숫자와는 비교될 숫자가 없는 것이니 queue에 삽입합니다.

 

#include <queue>
#include <cstdio>
#include <vector>
using namespace std;
 
vector<int> v[32001];
int in[32001];
queue<int> q;
 
int main() {
    int N, M, a, b;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        in[b]++;
    }
    for (int i = 1; i <= N; i++) {
        if (in[i] == 0) {
            q.push(i);
        }
    }
 
    while (!q.empty()) {
        int parent = q.front();
        q.pop();
        printf("%d ", parent);
        for (int i = 0; i < v[parent].size(); i++) {
            int child = v[parent][i];
            in[child]--;
            if (!in[child]) q.push(child);
        }
    }
}