[백준 2252번] 줄 세우기

문제 링크: https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

<문제 풀이> 그래프, 위상 정렬

위상 정렬 알고리즘을 그대로 적용하면 되는 문제입니다.

 

1. indegree가 0인 정점을 모두 큐에 넣는다.

2. 큐가 빌 때까지 다음을 반복한다.

3. 큐에서 정점을 하나 꺼낸다.

4. 꺼낸 정점을 결과 리스트에 넣고 정점의 인접 리스트를 확인한다.

5. 꺼낸 정점과 연결된 다른 정점의 indegree을 1 감소시킨다.

5. 만약 연결된 정점의 indegree를 1 감소시켰을 때 indegree가 0이 되면 그 정점을 큐에 넣는다. 

 

<C++ 소스 코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
 
int indegree[32001];
vector<int> adj[32001];
vector<int> res;
int n, m;
 
void solve() {
    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();
        res.push_back(cur);
        for (auto& next : adj[cur]) {
            indegree[next]--;
            if (!indegree[next])q.push(next);
        }
    }
    
}
 
int main(void) {
    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;
        adj[a].push_back(b);
        indegree[b]++;
    }
    solve();
 
    for (auto& e : res) {
        cout << e << " ";
    }
 
 
    return 0;
}