[Algorithm] 위상정렬(그래프 정렬)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Solve

ㅇ위상정렬

- 어떤 일을 하는 순서를 찾는 알고리즘

- 각각의 일의 선후관계가 복잡하게 얽허있을 때 각각 일의 선후관계를 유지하면서 전체 일의 순서를 짜는 알고리즘

  (그래프를 이용하여 일의 순서를 정할 때 주로 사용)

- 순서가 지켜져야하므로 인접행렬 방향 그래프 사용

입력이 다음과 같을 때,

6 6

1 4 (1번 작업 수행 후 4번 작업 진행)

5 4 

4 3 

2 5 

2 3 

6 2

아래와 같은 그래프가 그려진다.

위상정렬에서는 진입차수, 들어오는 간선이 중요한데(차수 : 연결된 간선의 개수)

위 그림에서 4번 노드를 보면 진입차수가 2이다.

여기서 진입차수에 있는 노드들(1번, 5번)의 작업이 끝나야 다음 작업(4번)이 진행될 수 있다.

입력 값들로 먼저degree배열에 진입차수의 개수를 저장해보자. 

1 4 

5 4 

4 3 

2 5 

2 3 

6 2

노드 2는 1개(6번)의 진입차수를 가지고 있고,

노드 3은 2개(4번, 2번)의 진입차수를 가지고 있고,

노드 4는 2개(1번, 5번)의 진입차수를 가지고 있고,

...

이제 동작을 시켜보자.

우선 위상정렬을 하는 과정에서는 Queue가 필요하다.

 

각 노드들의 진입차수를 확인하면서 진입차수가 0인 노드를 먼저 Queue에 넣어준다.

1번, 6번 노드가 Queue에 들어간다.

 

Queue에 있는 원소들을 하나씩 빼면서 출력해주고,

연결된 간선을 지워준다.

1번 노드는 4번 노드와 연결되어있으므로 4번 노드의 진입차수는 1이 줄어들 것이다.

 

다음으로는 Queue에 들어있는 6을 빼면서 출력해주고,

2번 노드와 연결된 간선을 지우면서

2번 노드의 진입차수는 1 줄어들게 된다.

여기서 2번 노드는 진입차수가 0이 되는데, 진입차수가 0이 되면

바로 Queue에 넣어준다.

 

다시 Queue에 들어있는 2를 빼면서 출력해주고,

2번 노드와 연결된 간선을 지워준다.

3번, 5번 노드의 진입차수는 1씩 줄어들 것이다.

여기서 5번 노드의 진입차수는 0이 되어 Queue에 들어간다.

 

마찬가지로 Queue에 들어있는 5를 빼면서 출력해주고,

...

위 설명대로 동작시켜보면

 

 

Queue가 빈 상태가 된다면 프로그램을 종료시켜주면 된다.

일의 순서는 1, 6, 2, 5, 4 와 같이 정할 수 있다.

 

#. Code

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int main(void)
{
    int N, M, i, a, b, now;
    freopen("input.txt", "rt", stdin);
    scanf("%d %d", &N, &M);
    vector<vector<int> > graph(N+1);
    vector<int> degree(N + 1);
    queue<int> q;
 
    for (i = 1; i <= N; i++) {
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        degree[b]++;
    }
 
    for (i = 1; i <= N; i++) {
        if (!degree[i]) q.push(i);
    }
 
    while (!q.empty()) {
        now = q.front();
        q.pop();
        printf("%d ", now);
 
        for (i = 0; i < graph[now].size(); i++) {
            int tmp = graph[now][i];
            degree[tmp]--;
 
            if (!degree[tmp])
                q.push(tmp);
        }
    }
 
    puts("");
    return 0;
}

line 15~19) 입력받은 그래프 정보를 저장

line 17) 그래프의 연결 정보를 2차원 벡터에 저장

line 18) 진입차수가 있는 노드의 진입차수 증가

line 21~23) 진입차수가 0인 노드먼저 동작시키기 위해 Queue에 push

line 25~37) Queue가 빌 때까지 반복

line 26~28) Queue에 있는 원소(우선순위를 가진)를 빼내고 출력

line 30~36) 해당 노드와 연결된 간선을 지우는 효과로, 해당 노드와 연결된 노드의 진입차수를 감소

line 34~35) 진입차수가 0이 된 노드가 있다면 Queue에 push

#. Other code

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);    
    int n, m, a, b, score;
    cin>>n>>m;
    vector<vector<int> > graph(n+1, vector<int>(n+1, 0));
    vector<int> degree(n+1);
    queue<int> Q;
    for(int i=0; i<m; i++){
        cin>>a>>b;
        graph[a][b]=1;
        degree[b]++;
    }
    for(int i=1; i<=n; i++){
        if(degree[i]==0) Q.push(i);
    }
    while(!Q.empty()){
        int now=Q.front();
        Q.pop();
        cout<<now<<" ";
        for(int i=1; i<=n; i++){
            if(graph[now][i]==1){
                degree[i]--;
                if(degree[i]==0) Q.push(i);
            }
        }
    }
    return 0;
}

#. Result

  - Input --------------------------------------------------------

6 6

1 4 

5 4 

4 3 

2 5 

2 3 

6 2

------------------------------------------------------------------

  - Output --------------------------------------------------------

1 6 2 5 4 3

------------------------------------------------------------------