[Algorithm]Baekjoon 2623번 :: 음악프로그램

https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

 
using namespace std;
 
int n, m;
vector<vector<int>> graph(1001);
int inDegrees[1001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i)
    {
        int count, input, prev;
        cin >> count;
 
        for (int i = 0; i < count; ++i)
        {
            cin >> input;
 
            if (i == 0)
            {
                prev = input;
                continue;
            }
 
            ++inDegrees[input];
            graph[prev].push_back(input);
            prev = input;
        }
    }
 
    queue<int> q;
    vector<int> answer;
 
    for (int i = 1; i <= n; ++i)
    {
        if (inDegrees[i] == 0)
        {
            answer.push_back(i);
            q.push(i);
        }
    }
    
    while (!q.empty())
    {
        int curNode = q.front();
        q.pop();
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i];
 
            --inDegrees[nextNode];
 
            if (inDegrees[nextNode] == 0)
            {
                answer.push_back(nextNode);
                q.push(nextNode);
            }
        }
    }
 
    if (answer.size() != n)
    {
        cout << 0;
    }
    else
    {
        for (int i = 0; i < answer.size(); ++i)
        {
            printf("%d ", answer[i]);
        }
    }
}

 

쉬운 위상정렬문제이다. 그래프탐색형식으로도 풀수는 있는데, 좀 더 복잡해지니 굳이 하지는 않았다.

처음 input값을 토대로 inDegrees배열을 업데이트해주고, 0인것부터, 즉 처음부분부터 연결된 노드들을 꺼내면서 --inDegrees를 해준다. --를 해줬을 때 연결된노드도 inDegrees값이 0이되면 push와 answer벡터에 넣어준다.

 

모든과정을 마쳤을 때 answer의 크기가 n과 같으면 정상적인 순서를 이뤘다고 판별할 수 있다.

n과 크기가 다르다면(더 작다면) 그래프형태가 싸이클을 이루기 때문에 건드리지 못한 노드가 있다는 것이기 때문에 정상적으로 순서를 만들 수 없으니 그냥 0을 출력하면 된다.