[Algorithm] 위상정렬(Topology Sort)

백준을 풀다가 위상정렬 문제가 나와서 간단하게 정리를 해봤다.

 

📌 위상정렬(Topology Sort)이란?

---

'순서가 정해져 있는 작업'을 차례로 수행해야 할 때, 그 순서를 결정해주기 위한 알고리즘.

 

✅ 작업의 순서가 정해져 있을 때, 작업을 정확하게 정렬해주는 알고리즘이다.

✅ 경로에 따라 여러개의 답이 존재할 수 있다.

✅ 사이클이 없는 방향그래프인 DAG(Directed Acyclic Graph)에만 적용이 가능하다.

 

🔆 결과값으로 1️⃣ 현재 그래프가 위상정렬이 가능한지, 2️⃣ 정렬이 가능하다면 그 결과는 무엇인지를 알 수 있다.

 

✔️ 위상정렬 구현 방법

위상정렬을 구현하는 방법으로는 두가지가 있는데,

1. Stack으로 구현

2. Queue로 구현

 

대부분 큐로 구현하는 것 같아, 여기서는 큐로 구현하는 것만 다루려한다.

 

 

✔️ 큐로 위상정렬 구현하기

1. 진입차수가 0인 정점 큐에 삽입
2. 큐에서 꺼내서 연결된 모든 간선 제거
3. 간선 제거 이후 진입차수가 0이된 정점 큐에 삽입
4. 큐가 빌 때까지 2번~3번 과정 반복
   모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상정렬의 결과값이다.

 

이 과정을 이용해서 문제를 풀어보자!

다음은 위상정렬을 이용하는 문제인 <선수과목> 이다. 링크

14567번: 선수과목 (Prerequisite)

 

1. 우선 그래프 형태로 입력을 해준다.
2. 입력을 해줄때, 두번째 값이 선수과목이 필요한 과목이므로 진입차수를 증가시켜준다.
3. 큐에 진입차수가 0인 과목들을 차례대로 넣어준다.
4. 하나씩 큐에서 꺼내면서 (꺼낸 과목이 1이라고 가정시), 해당 과목(1)을 선수과목으로 가지는 다른 과목들을 탐색한다.
5. 진입차수를 하나씩 감소시킨다. 진입차수가 0이 된다면 마찬가지로 큐에 넣어준다.
6. 큐가 빌때까지 반복한다.

 

문제에는 없지만, 만일 큐가 비었지만 과목이 남았다면, 사이클이 존재한다는 걸 알 수 있다.

이번 코드는 그럴일이 없기 때문에 넣지 않았지만,

만약 사이클을 검증하는 일이 필요하다면, 큐가 빌때까지 반복문을 도는 것이 아니라 과목의 개수만큼 반복문을 돌면서 큐가 비었는지 안비었는지 확인하면 된다.

 

 

<코드>

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m;
int indegree[500001];
int result[500001];
vector<int> v[500001];

void topology()
{
    queue<int> q;
    for(int i=1; i<=n; i++) {
        //진입차수가 0인 과목들을 순차적으로 큐에 넣어주고
        if(indegree[i] == 0) {
            q.push(i);
            //결과값을 1로 해준다.
            result[i] = 1;
        }
    }
    //큐가 빌때까지 반복문을 돌려준다.
    while(!q.empty())
    {
        //큐에서 하나씩 뽑아준다.
        int now = q.front();
        q.pop();

        //해당 과목을 선수과목으로 가지는 과목들을 탐색한다.
        for(int i=0; i<v[now].size(); i++) {
            //차례대로 탐색중
            int next = v[now][i];
            //진입차수를 하나 내려준다.(학기 지남)
            indegree[next] -= 1;
            //만약 진입차수==0이면 선수과목이 존재하지 않으므로 큐에 넣어주고 결과값을 저장한다.
            if(indegree[next]==0) {
                q.push(next);
                result[next] = result[now] + 1;
            }
        }
    }

    //결과값 출력 코드
    for(int i=1; i<=n; i++) cout << result[i] << " ";
} 

int main(void)
{
    ios::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;
        v[a].push_back(b);
        indegree[b]++;
    }

    topology();

    return 0;
}