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

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입출력

• 예제 입력 1

3 2
1 3
2 3

• 예제 출력 1

1 2 3

• 예제 입력 2

4 2
4 2
3 1

• 예제 출력 2

4 2 3 1

Solution

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

int indegree[MAX];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    
    vector<int> v[MAX];
    queue<int> q;
    vector<int> answer;

    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        indegree[b]++;
    }

    for (int i = 1; i <= N; i++) {
        if (indegree[i] == 0) {
            answer.push_back(i);
            q.push(i);
        }
    }

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < v[x].size(); i++) {
            indegree[v[x].at(i)]--;
            if (indegree[v[x].at(i)] == 0) {
                q.push(v[x].at(i));
                answer.push_back(v[x].at(i));
            }
       }
    }
    for(auto i : answer) cout << i << '\n';
    return 0;
}

Topological Sort, 위상정렬 문제다. 몇 가지 순서만을 보고 정답을 유추해내는 방법이고, 정답은 다양하게 나올 수 있다. 애초에 출력 조건에 답이 여러개면 아무거나 출력하라 했으니 위상정렬을 쓰는 것 또한 쉽게 파악할 수 있다 .

for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    indegree[b]++;
}

a보다 b가 앞에 선다는 의미다. 총 M번 입력받는다. 뒤에 서는 게 확정 된 b에 대해 indegree 값을 증가시킨다.

 for (int i = 1; i <= N; i++) {
    if (indegree[i] == 0) {
        answer.push_back(i);
        q.push(i);
    }
}

만약 어떤 노드의 뒤에 있지 않을 게 확실한 노드가 있다면 그 노드를 우선 answer vector에 저장하고 Queue에도 저장한다.

 while (!q.empty()) {
     int x = q.front();
     q.pop();
     for (int i = 0; i < v[x].size(); i++) {
         indegree[v[x].at(i)]--;
         if (indegree[v[x].at(i)] == 0) {
             q.push(v[x].at(i));
             answer.push_back(v[x].at(i));
        }
   }
}

Queue에는 indegree값이 따로 추가되지 않은 노드들이 저장되어있다. Queue에 있는 노드를 하나씩 빼가며 그 노드와 연결되어있는, 즉 그 노드 뒤에있다는 게 확실한 노드들을 체크해가며 그 노드들의 indegree 값을 줄인다. 그 후 그 값이 0이 되었다면 그 값을 Queue에 집어넣고 answer vector에 저장한다.

모든 순서를 알지는 못하지만 몇 가지 순서만 알고있다면 이런 식으로 가능한 순서를 출력해 낼 수 있다. 입력 순서에 따라서 정답이 다르게 나올 수도 있는 게 위상정렬의 특징.