[백준] [C++] 2623번 음악프로그램 (DFS, 위상정렬, 사이클, DAG)

 

1. 문제

 

2623번: 음악프로그램 (acmicpc.net)

2623번: 음악프로그램

 

 

2. 간략한 풀이

이 문제는 각각 PD들이 주는 목록들을 합쳐

 

트리로 만들고, 그 트리를 위상정렬하면 자연스럽게 모든 pd의 요구사항을 만족할 수 있다.

 

하지만, PD들 서로의 목록에 모순(순환, 사이클) 이 있는 경우 모든 pd들의 요구사항을 만족할 수 없으니.

 

위상정렬을 하면서 사이클 존재 여부 또한 검사해야한다.

 

 

3. 위상 정렬

 

맨 마지막 노드인 리프를 제일 끝에 두는 방법이 일반적인 위상 정렬의 방법이다.

 

리프 노드들을 결과를 저장할 배열의 끝에 넣고, 트리에 제외하면서 다음 리프노드를 찾는것을 반복하면 결국

 

배열에는 위상 정렬된 트리를 얻을 수 있다.

 

 

이러한 알고리즘은 dfs를 사용하면 쉽게 구현할 수 있다.

 

dfs 함수 종료 직전에 노드를 스택에 담는것이다.

 

dfs를 재귀적으로 구현할 때, 가장 처음 종료되는 dfs의 노드는 리프노드이기 때문에 

 

스택에 리프노드들이 먼저 들어가게된다.

 

따라서 dfs를 마친 후에 

 

이 스택을 위에서부터 출력하면,  위상정렬된 결과를 얻을 수 있다. 

 

 

 

4. 사이클 존재 여부 

위상정렬을 만들어가면 사이클 존재여부 또한 쉽게 알 수 있다.

 

1) 다음 노드. 이미 방문했지만, 위상정렬 스택에 이 노드가 없음.

2) 다음 노드, 이미 방문했지만, 위상정렬 스택에 이 노드가 있음.

 

 

1번의 경우는 현재 노드가 다음 노드의 자손이라는 뜻이며, 사이클이 존재한다는 것이다.

(자손이 부모가됨)

 

2번의 경우는 현재 노드가 다음 노드에 독립적이라는 뜻이다.

 

 

 

5. 코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <stack>
 
using namespace std;
 
vector<vector<bool> > adjlist;
vector<bool> visited;
vector<int> s;
 
 
bool dfs(const int& x) {
    visited[x] = true;
    for(int i = 0 ; i < adjlist[x].size(); i++) {
        if(adjlist[x][i] == false) continue;
        if(visited[i]) {
            auto iter = find(s.begin(), s.end(), i);
            if(iter == s.end())  return false;
        }
        else {
            if(!dfs(i)) return false;
        }
    }
    s.push_back(x);
    return true;
}
void dfsAll(int N) {
    visited = vector<bool>(N, false);
    for(int i = 0 ; i < N; i++) {
        if(!visited[i]) {
            if(!dfs(i)) {
                cout<<0;
                return;
            }
        }
    }
    for(int i = N-1; i >= 0; i--) {
        cout<<s[i]+ 1<<"\n";
    }
}
 
int main() {
    int N, M;
    cin>>N>>M;
    adjlist = vector<vector<bool> > (N, vector<bool>(N, false));
    for(int i = 0; i < M; i++) {
        int t;
        cin>>t;
        int a, b;
        for(int j = 0; j < t; j++) {
            cin>>a;
            a--;
            if(j != 0) {
                adjlist[b][a] = true;
            }
            b = a;
        }
    }
    dfsAll(N);
}