백준) 2252 줄 세우기

문제집

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

그래프가 유향 그래프라면, 노드 간에는 위상이 정해진다.

a노드에서 b노드로 진출하는 간선이 있다면, a와 b의 위상이 서로 다른 셈이다.

실생활에서 노드간의 위상은, 선수강과목이나 테크트리에서 찾아볼 수 있다.

넥서스가 있어야 게이트웨이를 지을수 있드시, 객체지향프로그래밍을 들어야 자료구조를 들을 수 있드시,

간선의 방향에 따라 노드간에 위상이 결정된다.

위상정렬은, 이와 같은 유향 그래프에서 노드 간의 위상을 순서대로 구하는 알고리즘이다.

따라서 유향그래프 내 사이클이 존재한다면, 즉 DAG이 아니라면 위상정렬할 수 없다.

여러가지 방법이 있지만, 주로 사용하는 진입차수를 이용한 풀이를 소개하고자 한다.

진입차수는 해당노드를 향한 간선의 개수를 뜻한다.

즉 1->3 // 2->3 의 간선이 있다면, 노드3의 진입차수는 2다.

위상정렬은 우선 모든 노드의 진입차수를 구하고 시작한다.

다음에는 진입차수가 0인 노드들을 전부 큐에 넣는다.

이제 큐에서 하나씩 꺼내면서 노드에서 나가는 간선들을 모두 제거한다.

현재 간선은 진입차수로 표현되었기 때문에, 진입차수를 표현하고 있는 데이터를 변경하면 되겠다.

제거하고 난 뒤 만약 진입차수가 0이 된 노드가 있다면 큐에 넣는다.

진입차수가 0인 노드들을 찾고, 딸린 간선을 제거하고,

다시 진입차수가 0인 노드들을 처리하는 부분문제로 이어진다고 생각하면 편하다.

사이클의 유무는 어떻게 판단할까?

만약 큐를 전부 소모했음에도 위상이 판단되지 않은 노드가 여전히 있다면 사이클때문임이 자명하다.

다음은 2252번 줄 세우기에 대한 해답이다.

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int n, m, a, b;
int in[32001];
 
int main() {
    scanf("%d %d", &n, &m);
    vector<vector<int>> edge(n + 1);
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        edge[a].push_back(b);
        in[b]++;
    }
 
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!in[i])
            q.push(i);
 
    while (!q.empty()) {
        int t = q.front();
        q.pop();
 
        printf("%d ", t);
 
        for (auto next : edge[t]) {
            in[next]--;
            if (in[next] == 0)
                q.push(next);
        }
    }
 
    return 0;
}