[C++] 2623번 음악프로그램 - 위상 정렬

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

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 1001

using namespace std;

int N, M;  //가수의 수 N, 보조 PD의 수 M
int num[MAX_N];  //공연 순서
vector<int> r[MAX_N];  //공연 순서
int inDegree[MAX_N];  //진입 차수
vector<int> res;  //위상 정렬 결과

void input()
{
    cin >> N >> M;
    LOOP(i, M) {
        int tmp;  //담당한 가수의 수
        cin >> tmp;
        LOOP(j, tmp)
            cin >> num[j];
        LOOP(j, tmp-1) {
            r[num[j]].push_back(num[j+1]);
            inDegree[num[j+1]]++;
        }
    }
}

void topologySort()  //위상 정렬
{
    queue<int> q;
    
    LOOP(i, N) {
        if(!inDegree[i]) q.push(i);
    }
    
    while(!q.empty()) {
        int x = q.front(); q.pop();
        res.push_back(x);
        for(int j=0; j<r[x].size(); j++) {
            int y = r[x][j];
            if(!(--inDegree[y])) q.push(y);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    
    topologySort();
    LOOP(i, N) {
        if((inDegree[i])) {
            cout << 0; return 0;
        }
    }
    LOOP(i, N) cout << res[i-1] << '\n';
    
    return 0;
}

솔직히 위상정렬 문제 한 문제라도 풀어봤으면 바로 풀 수 있을 것 같다. 지금까지 풀어온 것과는 다른 점이 있다면 불가능한 경우는 어떻게 되는가? 

 

불가능한 경우에는 진입 차수가 0이 되지 않더라도 위상 정렬과정에서 큐가 비는 현상이 발생하게 된다. 이는 회로가 발생하였기 때문이다. 따라서 이를 확인해주면 문제는 쉽게 풀린다.

 

 

<위상 정렬>

https://leyamon.tistory.com/entry/C-2252%EB%B2%88-%EC%A4%84-%EC%84%B8%EC%9A%B0%EA%B8%B0-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC?category=957621 

[C++] 2252번 줄 세우기 - 위상 정렬

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.