[백준 2252] 줄 세우기

0. 제목

• 백준 2252 줄 세우기
• BOJ 2252 줄 세우기
• C++ 2252 줄 세우기

---

1. 문제

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

---

2. 풀이

• Topological Sort(위상 정렬)을 사용하는 문제이다.
• 위상 정렬은 indegree 즉, 자신에게 들어오는 노드 수를 계산하고 indegree가 0이 되면 먼저 정렬해 주는 것이다.
• 위상 정렬의 특징 중 하나는 사이클이 생기면 안된다는 것이다. indegree가 모두 0보다 크면 사이클이 생긴다는 의미이다. 따라서 위상 정렬은 indegree가 0인 것이 하나 이상 존재할 때 가능하다.
• 이 문제에서 1 3 이 주어졌을 때 1 다음에 3이 줄을 서야 한다. 방향을 나타내면 1 -> 3 으로 나타낼 수 있고 이 상황에서 3의 indegree는 1이 된다.
• indegree는 연결 선을 구축하면서 화살표를 받는 방향에 1씩 추가 해준다. 
• 큐를 활용해서 구현하는데 먼저 indegree가 0인 노드 번호를 큐에 모두 push 한다.
• 그 후 큐가 빌때까지 반복을 하는데 위상정렬에서는 while 반복문을 한 번 돌때마다 indegree가 0인 것은 무조건 나오게 되어 있다. 사이클이 없다는 가정을 하였기 때문이다.
• 그렇게 0인것을 push 하고 pop 해주는 과정을 반복하면서 pop되는 노드번호들을 순서대로 출력해준다.

---

3. 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> graph[32001];
int inDegree[32001];
int N, M;
 
void TopologicalSort(void){
    queue<int> q;
    
    for(int i = 1; i <= N; i++)
        if(!inDegree[i])
            q.push(i);
        
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        cout << cur << ' ';
        for(int i = 0; i < graph[cur].size(); i++){
            inDegree[graph[cur][i]]--;
            if(!inDegree[graph[cur][i]])
                q.push(graph[cur][i]);
        }
    }
}
 
int main(int argc, const char * argv[]) {
    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;
        graph[a].push_back(b);
        inDegree[b]++;
    }
    
    TopologicalSort();
    
    return 0;
}