[위상정렬] 2623 음악프로그램

이 문제는 굉장히 장황하게 써있지만 해석을 해보자면 다음과 같다.

예제를 예로 설명 하면

맨처음에 6과 3이 입력되는데, 이 6은 노드의 개수이다.

총 6개의 노드가 있는데, 그 다음줄에 보면 1 4 3 이 입력된다. 1->4를 갈수 있고 4->3으로 갈수 있다는 의미이다.

마찬가지로

6->2 2->5 5->4 2->3 과 같은 그래프를 얻어 낼 수 있다.

위상 정렬이라는 것은 그래프에서 노드들의 순서를 뽑아내는 작업이다.

예를 들어 그래프가 6->2 2->5와 같이 연결되어 있다면 6번 노드를 처리한다음에야 2번 노드를 처리할수 있고 2번노드를 처리한 다음에야 5번노드를 처리할수 있다는 의미이다.

이런식으로 쭉 나열하게 되면 6번 2번 1번 5번 4번 3번 순서대로 처리를 하면 위의 조건을 모두 만족시키는 정렬이 된다.

하지만 위상정렬은 여러개가 나올 수 있다.

6 2 1 5 4 3 도 위 문제의 조건을 만족시키지만 1 6 2 5 4 3 도 위의 문제의 조건을 만족시킨다

보면 1번 을 처리한다음 4번을 처리하고 4번을 처리한다음 3번을 처리하기 때문에 문제 조건에 위배되지 않는다.

위상정렬이라는것은 DAG(Directed Acycling Graph) 방향 그래프인데, 싸이클이 없는 그래프에서만 적용이 가능하다.

만약에 그래프가 방향그래프인데 싸이클이 존재한다면 

예를들면 2->5->3->2 와 같은 루프가 존재한다면 위상 정렬을 할 수 없게 된다. 2번을 처리해야 5번을 처리할수 있고 5번을 처리해야 3번을 처리할수 있고 3번을 처리해야 2번을 처리할수 있다는 뜻이 되는데,

그럼 결국에 2번을 처리해야 2번을 처리할수 있다는 이상한 의미가 되어버린다.

따라서 위상 정렬을 하기 위해선 무조건 싸이클이 없어야 한다. 알고리즘 상에서 이것을 어떻게 판별하는지 알아보자.

위상 정렬은 각 노드의 입차수(몇개의 엣지가 나를 향해 있는가)를 기준으로 정렬한다. 

알고리즘의 순서는 다음과 같다.

먼저 BFS를 활용해서 문제를 푼다.

1.큐에 원소 하나를 추출한다.(이 원소는 입차수가 0인 노드의 인덱스이다.)

2.그 노드에서 출발하는 모든 엣지를 지워준다.(지워준다의 의미는 그 노드의 엣지에 연결된 모든 노드의 입차수를 하나 줄여준다는 뜻)

3.그리고 나서 그 입차수가 하나 줄어들게된 노드의 입차수가 0이되면 다시 큐에 그 노드의 인덱스를 집어 넣는다.

위의 과정을 큐가 빌 때 까지 반복하게 된다.

따라서 각 노드의 입차수를 저장하기 위한 배열이 하나 필요하고(indegree), 각 노드에서 어떤 노드로 연결되어 있는지를 저장하기 위한 2차원배열이 필요하다(이것은 벡터 배열로 구현하였다,v[])

또한 결과를 저장하기 위한 벡터(result벡터)와 큐 하나 이렇게 총 4개의 자료구조가 필요하다 

알고리즘을 돌리면서 그래프에 싸이클이 있는것을 판단하는 방법은 다음과 같다.

만약에 그래프에 싸이클이 존재한다면, 위상정렬을 끝마치기 전에 큐가 비게 되어서 프로그램이 종료 되게 된다.

따라서, while문이 종료 되었을때 결과 벡터에 몇개의 원소가 저장되어 있는지 확인하게 되면 그래프에 싸이클이 존재하는지 안하는지를 확인할수 있다. ( 싸이클이 있는 그래프에 대해 위의 알고리즘대로 따라가보자. 노드의 개수가 6개일때 result벡터에 6개의 노드를 채우지 못한채로 종료하게 된다.)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[1001]; //2차원 배열 
queue<int> q;
int indegree[1001]; //입차수 저장 배열
 
 
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> result; // 위상 정렬된 노드들이 들어갈 벡터. 
    for (int i = 0; i < m; i++) {
        int temp; cin >> temp;
        int before, cur;
        cin >> before;
        for (int j = 0; j < temp-1; j++) {
            cin >> cur;
            v[before].push_back(cur); // before -> cur 갈수 있음 표시.
            indegree[cur]++;
            before = cur;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
            result.push_back(i);
        }
    }
    
    while (!q.empty()) { //BFS
        int index = q.front(); q.pop();
        for (int k : v[index]) { // index번째 노드와 연결된 노드를 탐색.
            //k는 index번째 노드와 연결된 노드의 인덱스
            indegree[k] --;
            if (indegree[k] == 0) {
                q.push(k);
                result.push_back(k);
            }
        }
    }
 
    if (result.size() == n) {
        for (int i = 0; i < result.size(); i++)
            cout << result[i] << endl;
    }
    else {
        cout << 0 << endl;
    }
 
 
    return 0;
}