[백준] 2623번 음악프로그램 C++ 문제풀이

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

2623번: 음악프로그램

 

문제 풀이

이 문제는 위상 정렬을 이용해 푸는 문제이다. 

가수의 순서가 결정되어 있는 상황에서 가수의 순서를 모두 만족하는 출현 순서를 출력해야하기 때문이다.

따라서  진입차수가 0이 되는 가수들부터 먼저 출력을 해주고, 그 가수와 연결된 가수들의 간선을 줄여주면서 queue가 비어질때까지 반복 수행하면 된다.

이 문제의 주의점은 순서를 정하는 것이 불가능한 경우가 존재한다는 것이다.

위상정렬은 순서가 비순환 방향 그래프에서만 사용이 가능하므로, 비순환 방향 그래프가 아닌 경우 0을 출력해주면 된다.

소스 코드

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

int indegree[1001] = { 0 };
vector<int> singer[1001];
queue<int> q;

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int num;
		cin >> num;
		vector<int> sunseo;
		for (int j = 0; j < num; j++) {
			int t;
			cin >> t;
			sunseo.push_back(t);
		}
		for (int j = 0; j < sunseo.size() - 1; j++) {
			int x = sunseo[j];
			int y = sunseo[j + 1];
			singer[x].push_back(y);
			indegree[y] += 1;
		}
	}
	// queue에 진입차수가 0인 정점 삽입
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) {
			q.push(i);
		}
	}

	vector<int> dag; // 가수의 순서를 담는 vector
	//위상 정렬
	while (!q.empty()) {
		int idx = q.front();
		dag.push_back(idx);
		q.pop();

		for (int i = 0; i < singer[idx].size(); i++) {
			int dy = singer[idx][i];
			indegree[dy] -= 1;
			if (indegree[dy] == 0) {
				q.push(dy);
			}
		}
	}

	// 비순환 방향 그래프인지 확인하는 과정.
	if (dag.size() != n) { 
		cout << 0 << '\n'; // 비순환 방향 그래프가 아니라면 0을 출력
	}
	else {
		for (auto x : dag)
			cout << x << '\n';
	}

}