[C++] 그래프 - 위상정렬(그래프 정렬)

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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

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]++;//degree배열에 진입배열 몇개있는지 카운팅함
    }
    for(int i = 1; i <= n; i++){
        if(degree[i] == 0) Q.push(i);
        //진입차수가 없다면(선행작업이 없다면 push)
        //선행작업이 없어야 일을 할 수 있으므로(다른건 1번일을 하고 난 후 4번일을 해야함)
    }
    
    while (!Q.empty()) {
        int now = Q.front();//Q엔 진입차수가 없는 값들이 담겨있음 여기서 하나 뺌
        Q.pop();
        cout << now << " ";//출력함
        for(int i = 1; i <= n; i++){
            //now가 만드는 진입차수를 하나 뺌 1->4라면 degree 4하나 감소 1을 했으므로
            if(graph[now][i] == 1){
                degree[i]--;
                if(degree[i] == 0) Q.push(i); //그와 동시에 선행작업 없는 애를 Q에 넣음4
            }
        }
    }
    return 0;
}

풀이

1. 인접행렬(or 인접리스트)로 그래프를 만든다.

2. degree 행렬은 진입차수를 의미한다. a에서 b로 이동하는 노드라면 b에는 진입차수가 하나 추가된다.

for(int i = 0; i < m; i++){
        cin >> a >> b;
        graph[a][b] = 1; //그래프화 시킴
        degree[b]++;//degree배열에 진입배열 몇개있는지 카운팅함
    }

3. 진입 차수가 없는 노드(선행해야할 일이 없는 작업)을 먼저 queue에 넣는다.

for(int i = 1; i <= n; i++){
    if(degree[i] == 0) Q.push(i);
    //진입차수가 없다면(선행작업이 없다면 push)
    //선행작업이 없어야 일을 할 수 있으므로(다른건 1번일을 하고 난 후 4번일을 해야함)
}

4. queue에 저장된 노드(진입차수가 0인 노드)를 하나 빼와서 출력한다(일을 했다는 의미)

5. 빼내온 노드와 연결된 노드를 찾고, 연결된 노드의 진입 차수를 하나 감소시킨다.(일을 했으므로)

6. 연결된 노드의 진입차수를 감소시켰는데 진입차수가 0인 노드가 됐다면 그 노드를 queue에 넣는다. 끝.

while (!Q.empty()) {
        int now = Q.front();// 4.
        Q.pop();
        cout << now << " ";//출력함
        for(int i = 1; i <= n; i++){
            if(graph[now][i] == 1){
                degree[i]--; // 5.
                if(degree[i] == 0) Q.push(i); //6.
            }
        }
    }

 

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