백준 2252 줄 세우기 (위상정렬)

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

⭐ 문제 요약

• 이 문제를 읽어보고 요약하면 이런 것이다.
• 학생들이 N명 있고 아래와 같은 정보가 M개가 주어진다.
• 1이 2보다 키가 크다, 2가 3보다 키가 크다, ...
• 그리고 그 M개의 조건을 위배하지 않는 순서대로 학생들을 출력하는 문제이다.
• 답은 여러가지가 존재하고, 그 중에 하나의 답만 출력하면 된다.

🪜 STEP 1

이걸 단순히 아이디어 없이 정렬하려고 하면 상당히 어렵다.
어떻게 정렬해야 할 지 감이 안오게 된다.
단순히 이런 방식을 생각해볼 수 있기는 하다.
먼저 1,2,3,4,5..., N까지 값이 있는 배열을 둔다.
그리고 M개의 조건을 하나 하나 읽을 때마다 그 조건에 성립하는지 확인한다.
성립하지 않으면 성립하도록 만든다.
이런식으로 로직을 짜면 1개의 조건을 읽을 때마다 N개의 요소를 확인해야 한다.
그래서 총 시간복잡도가 O(N x M)이다.
그러면 3 x 10^9 정도가 되어버리므로 30초가 걸리므로 TLE(Time Limited Exceeded)가 날 것이다.

🪜 STEP 2

그러면 시간 복잡도를 줄 일 아이디어가 필요하다.
이전 아이디어는 단순히 조건을 하나하나 읽을 때마다 배열을 검사했다.
이번에는 조건을 좀 더 깊게 고민해보자. M개의 조건은 학생들의 순서를 표현한다.
이 조건을 한 눈에 이해하기 위해서 그래프로 표현할 수 있을 것이다.

🪜 STEP 3 : 문제 풀이

학생을 노드로 보고 키 정보를 엣지로 표현해볼 수 있겠다.
그러면 사이클 없는 방향 그래프임을 알 수 있다...!!
그리고 그 그래프에서 각 노드의 순서를 정렬하는 문제가 된다.
그 문제는 위상 정렬로 풀 수 있다.
선행순서를 위배하지 않으면서 모든 노드를 순서대로 정렬하는 것을 위상정렬이라고 한다.
위상정렬 방법은 Kahn 알고리즘(BFS 기반)과 DFS 기반이 있으며,

먼저 알고리즘을 이해하기 위해선 진입차수에 대해 알아야 한다.
진입 차수는 외부에서 어떤 노드로 향하는 엣지의 개수이다.
단순히 아래와 같은 그래프에서는
7,8,9의 진입 차수는 0이고,
2,3,6의 진입 차수는 1이고
1,4,5의 진입 차수는 2이다.

Kahn 알고리즘은 다음과 같은 방식으로 작동한다.
진입차수 0인 노드를 전부 찾아 BFS방식으로 depth를 한 단계씩 늘려가며 출력한다. 즉, 7, 8, 9를 출력하고, 5 ,6 을 출력하고, 3, 4를 출력하고, 1을 출력하고, 2를 출력한다.

• 큐에 진입차수 0인 노드를 전부 푸시한다.
• 큐에서 팝하고, 그 노드의 인접 노드를 아래 로직으로 전부 순회한다.
• 인접노드의 진입차수를 -1 한다.
• 인접노드의 진입차수가 0이라면 큐에 푸시한다.

 

📜 코드

아래와 같은 입력 데이터로 문제를 설명하면 아래와 같이 된다.

 

입력데이터
9 9  
7 5  
8 5  
9 6  
5 3  
5 4  
6 4  
3 1  
4 1  
1 2  
출력데이터
7 8 9 5 6 3 4 1 2

 

#include <bits/stdc++.h>  
using namespace std;  

int N, M;  
vector<vector<int>> adj_list;  
vector<int> indegree;  
queue<int> q;  
void BFS() {  
    for (int i = 1; i <= N; i++) if (indegree[i] == 0) q.push(i);  
    while (!q.empty()) {  
        int current_node = q.front(); q.pop();  
        cout << current_node << " ";  
        for (int next_node : adj_list[current_node]) {  
            indegree[next_node]--;  
            if (indegree[next_node] == 0) q.push(next_node);  
        }  
    }  
}  

int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(NULL);  
    cout.tie(NULL);  

    cin >> N >> M;  
    adj_list.resize(N + 1);  
    indegree.resize(N + 1);  


    for (int i = 0; i < M; i++) {  
        int start, end;  
        cin >> start >> end;  
        adj_list[start].emplace_back(end);  
        indegree[end]++;  
    }  
    BFS();  

    return 0;  
}