백준 2251 - 줄 세우기, C++, 위상정렬

2252번: 줄 세우기

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

int n, m;
int from, to;
int inCome[32001];
vector<int> node[32001];

void TopologySort(){
    queue<int> q;

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

    while (!q.empty()){
        int cur = q.front();
        q.pop();

        cout << cur << " ";

        for(int i = 0; i < node[cur].size(); i++){
            int nextCur = node[cur][i];
            inCome[nextCur]--;

            if(inCome[nextCur] == 0)
                q.push(nextCur);
        }
    }
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(inCome, 0, sizeof(inCome));
    // input
    cin >> n >> m;

    for(int i = 0; i < m; i++){
        cin >> from >> to;
        inCome[to] = inCome[to] + 1;
        node[from].push_back(to);
    }

    // solve
    TopologySort();
    cout << '\n';

    return 0;
}

---

 대표적인 백준의 위상 정렬 문제입니다. 이전까지는 위상 정렬 이름이 어려워 보이니깐 공부를 하지 않고 미루고 있었는데 생각 외로 쉬운 개념이라서 금방 이해한 후 풀 수 있었습니다.

 

1. 입력을 받으면서 각 노드에 진입하는 간선이 몇개인지 계산해 둡니다.

2. 이후 정렬의 시작을 결정할 간선들은 '자신으로 들어오는 간선이 없는 노드' 가 되며 이것들을 전부 큐 안에 넣어둡시다.

3. 이후 큐에서 하나씩 노드를 빼면서 노드에 연결된 지점들을 계속 비교하며 아래 2가지 동작을 합니다.

    3-1. 다음 노드에 대해서 '자신에게 오는 간선'을 저장한 배열의 값을 1 줄여줍니다.

    3-2. 이후 다음 노드가 '자신에게 오는 간선'이 0 이라면 선행 작업을 다 한걸로 간주해 큐에 넣어줍니다.