골드2 - 백준 2623 음악프로그램

백준 2623 음악프로그램

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

접근방법

이 문제는 저번에 풀었던 문제집 문제와 똑같은 방식으로 풀면 되겠다는 생각이 들었다. 큐를 사용해서 선행되어야 하는 가수가 없는 가수를 큐에 넣어주고 차례대로 꺼내면서 선행 가수들에 대한 정보를 갱신하여 큐에 넣어가는 식으로 문제를 진행했다.

풀이

musician 배열은 각 가수 이전에 출연해야 하는 가수의 수를 저장하고 있고 이 수가 0이 되었을 때, queue에 추가되어 순서를 기다린다.
front의 이차원 백터에 해당 가수가 출연하면 그 뒤에 출연할 수 있는 가수들을 저장해주었고, 큐의 앞에서 꺼내어 출연시키면 result 백터에 저장 후에 연관된 가수들의 musician 배열에 -1씩 감소시켜주었다.

queue가 비게 된다면 result 백터를 출력해주었다.

코드

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

using namespace std;

int musician[1001];
vector<vector<int>> front;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N, M;
	cin >> N >> M;

	for (int i = 0; i <= N; i++)
	{
		vector<int> temp;
		front.push_back(temp);
	}

	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;

		int before;
		for (int j = 0; j < num; j++)
		{
			if (j == 0) {
				cin >> before;
				continue;
			}

			int cur;
			cin >> cur;
			front[before].push_back(cur);
			before = cur;
			musician[cur]++;
		}
	}

	queue<int> q;
	
	for (int i = 1; i <= N; i++)
	{
		if (musician[i] == 0)
			q.push(i);
	}

	vector<int> result;
	while (!q.empty())
	{
		int cur = q.front();
		result.push_back(cur);
		q.pop();

		for (int i = 0; i < front[cur].size(); i++)
		{
			musician[front[cur][i]]--;
			if (musician[front[cur][i]] == 0)
				q.push(front[cur][i]);
		}
	}

	if (result.size() != N)
		cout << 0 << '\n';
	else
	{
		for (int i = 0; i < result.size(); i++)
			cout << result[i] << '\n';
	}
	return 0;
}