백준 2252번 줄 세우기 - C++(cpp) 풀이

1. 각 학생을 그래프의 정점으로 생각한다.
2. A가 B의 앞에 서야 한다면, A에서 B로 가는 방향 간선을 추가한다.
3. 위상 정렬한 결과를 출력한다.

---

1. 각 학생을 그래프의 정점으로 생각한다.

 각 학생을 그래프의 노드로 생각할 것이다. X번 학생은 X번 노드로.

 

2. A가 B의 앞에 서야 한다면, A에서 B로 가는 방향 간선을 추가한다.

 A가 B의 앞에 서야 한다면, A가 있은 뒤에 B가 와야 한다. 이것을 그래프에 표현하기 위해 A → B인 방향 간선을 추가한다.

 

3. 위상 정렬한 결과를 출력한다.

 이제 완성된 그래프를 위상 정렬한 결과를 출력하면 된다. 주어진 상황이 위상 정렬 상황이기 때문.

 

---

#include <iostream>
#include <queue>
#include <string.h>
#include <vector>

using namespace std;

int N, M;
int indegree[32001];
vector<int> edges[32001];

void topologySort() {
    queue<int> q;
    
    for (int i = 1; i <= N; i++) {
        if (indegree[i] == 0) q.push(i);
    }
    
    while (!q.empty()) {
        int current = q.front(); q.pop();
        
        cout << current << " ";
        
        for (int i=0; i<edges[current].size(); i++) {
            int end = edges[current][i];
            indegree[end]--;
            if (indegree[end] == 0) q.push(end);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    
    int A, B;
    for (int i=0; i<M; i++) {
        cin >> A >> B;
        edges[A].push_back(B);
        indegree[B]++;
    }
    
    topologySort();

    return 0;
}