[백준 C++] 2623번: 음악프로그램

1. 문제

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

2623번: 음악프로그램

 

2. 알고리즘 분류

• 그래프 이론
• 위상 정렬

 

3. 소스 코드

Key Point)
1. 순서가 정해져 있는 일련의 수열을 차례대로 출력하는 문제는 '위상 정렬' 알고리즘을 사용한다.

 

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

using namespace std;

int N, M;
int arr[1001];
int inDegree[1001];
int visited[1001];
vector<int> graph[1001];
vector<int> singers;

// 모든 원소를 방문하기 전에 큐가 비었다면 사이클이 존재
bool is_cycle()
{
	for (int i = 1; i <= N; i++)
		if (!visited[i]) return true;

	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 가수의 수(N)과 보조 PD의 수(M) 입력
	cin >> N >> M;

	// 보조 PD가 담당한 가수의 수와 가수들의 순서 입력
	for (int i = 0; i < M; i++)
	{
		int n;
		cin >> n;

		for (int j = 0; j < n; j++)
			cin >> arr[j];

		for (int j = 1; j < n; j++)
		{
			graph[arr[j - 1]].push_back(arr[j]);	// 그래프 입력
			inDegree[arr[j]]++;	// 진입 차수 계산
		}
	}

	// 위상 정렬
	queue<int> q;

	for (int i = 1; i <= N; i++)
	{
		if (!visited[i] && inDegree[i] == 0)
		{
			singers.push_back(i);
			visited[i] = 1;
			q.push(i);
			
			while (!q.empty())
			{
				int cur = q.front();
				q.pop();

				for (int j = 0; j < graph[cur].size(); j++)
				{
					int next = graph[cur][j];

					if (--inDegree[next] != 0 || visited[next]) continue;

					singers.push_back(next);
					visited[next] = 1;
					q.push(next);
				}
			}
		}
	}

	if (is_cycle())	// 사이클이 발생했다면(순서가 꼬였다면), 0을 출력
		cout << "0";
	else
	{
		for (int i = 0; i < singers.size(); i++)
			cout << singers[i] << "\n";
	}


	return 0;
}

 

4. 유용한 문법 및 알고리즘

	// 위상 정렬
	queue<int> q;

	for (int i = 1; i <= N; i++)
	{
		if (!visited[i] && inDegree[i] == 0)
		{
			singers.push_back(i);
			visited[i] = 1;
			q.push(i);
			
			while (!q.empty())
			{
				int cur = q.front();
				q.pop();

				for (int j = 0; j < graph[cur].size(); j++)
				{
					int next = graph[cur][j];

					if (--inDegree[next] != 0 || visited[next]) continue;

					singers.push_back(next);
					visited[next] = 1;
					q.push(next);
				}
			}
		}
	}