[백준] 2623 음악 프로그램(C++)

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

2623번: 음악프로그램

---

난이도 : 골드3

 

풀이 과정 :

위상정렬 문제로 사이클 여부 판별 + 중복간선 제거 를 해결해야되는 문제였습니다.

저는 맨처음엔 벡터로 하려다가 set자료형을 이용하여(중복을 허용하지 않음) set배열로 입력을 받았습니다.

만약에 중복된 간선이 나오면 삽입을 해도 set배열의 크기가 같으므로 만약 삽입을 했는데도 전에랑 크기가 같으면

진입차수를 저장하는 배열은 업데이트를 하지 않게 해주었습니다.

 

그리고 문제 나와있듯이 2->3, 3->2같은 경우가 나올 때 0을 출력하라고 되어있는데요,

위상정렬을 하기 위해서는 사이클이 존재하면 안되므로, 위상정렬에서 사이클을 판별하는 방법은 

위상정렬 큐에 들어가지 않은 원소가 있다면 사이클이 존재한다고 할 수 있습니다. (설명은 아래 링크 확인)

 

왜 위상 정렬을 이용하면 그래프 사이클이 있는지 판단할 수 있을까요? (tistory.com)

 

맨 처음에 진입 차수가 0이 아닌 게 없다면 사이클이 존재하는거 아닌가? 라고 생각하여 

진입차수가 0인걸 큐에 삽입하고 큐의 사이즈가 0일때 0을 출력하려고 했으나

부분적 사이클이 존재할 수있다는 반례를 깨닫고 출력을 했을 때

큐의 사이즈가 n과 같지 않다면 사이클이 존재한다고 바꿔주었습니다. ! 

 

#include <iostream>
#include <set>
#include <queue>
using namespace std;

int n, m, len[1005];
set<int> v[1005];
queue<int> q;
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int num;
        cin >> num;
        int s, e;
        cin >> s;
        for (int j = 0; j < num - 1; j++) {
            cin >> e;
            int cnt = v[s].size();
            v[s].insert(e);
            if (cnt != v[s].size()) len[e]++;
            s = e;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (len[i] == 0) q.push(i);
    }

	// 이해를 위한 set 배열 확인
  /*  for (int i = 1; i <= n; i++) {
        set<int>::iterator iter;
        cout << i << ": ";
        for (iter = v[i].begin(); iter != v[i].end(); iter++) {
            int next = *iter;
            cout << next << " ";
        }

        cout << "\n";
    }*/

    queue<int> ans;
    while (!q.empty()) {
        int here = q.front();
        q.pop();        
        ans.push(here);
        set<int>::iterator iter;
        for (iter = v[here].begin(); iter != v[here].end(); iter++) {
            int next = *iter;
            len[next]--;
            if (len[next] == 0) q.push(next);
        }
    }

    if (ans.size() != n) { cout << 0; } //사이클이 존재하면
    else {
        while (!ans.empty()) {
            cout << ans.front() << '\n';
            ans.pop();
        }
    }
}