BOJ 2623: 음악프로그램

#BOJ 2623: 음악프로그램

2623번: 음악프로그램

#풀이

조건에 맞춰 가수들의 순서를 정해야 하는 문제이다.

 

위상정렬을 사용할 수 있다.

위상정렬 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이므로 순서를 정할 때 사용할 수 있는 문제이다.

 

 

BOJ 2252 과 같은 맥락의 문제이다.

 

입력을 받을 때 가수 한명이 정점이라고 생각하고 인접리스트에 받는다.

 

예)

3 1 4 3
4 6 2 5 4
2 2 3

 

1->4, indegree[4]++

4->3, indegree[3]++

6->2, indegree[2]++

2->5, indegree[5]++

5->4, indegree[4]++

2->3, indegree[3]++

 

이렇게 생각하고 인접리스트에 저장한다. 또한 위상정렬을 사용하려면 indegree로 저장해야한다.

 

위상정렬이 할 수 없는 그래프는 사이클이 있는 그래프이다.

사이클이 있는 그래프는 위상정렬을 했을 때 모든 정점을 방문하지 않는다.

사이클을 찾는 것보다 위상정렬을 끝마쳤을 때 정점의 개수를 확인하는 것 이 좋다.

 

#코드

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

int n, m;
vector<int> adj[1001];
int indeg[1001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int sing_num, prev, nxt;
		cin >> sing_num;
		cin >> prev;
		for (int j = 1; j < sing_num; j++) {
			cin >> nxt;
			adj[prev].push_back(nxt);
			indeg[nxt]++;
			prev = nxt;
		}
	}
	queue<int>q;
	vector<int> sort_arr;
	for (int i = 1; i <= n; i++)
		if (indeg[i] == 0) q.push(i);

	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (auto nxt : adj[cur]) {
			indeg[nxt]--;
			if (indeg[nxt] == 0)
				q.push(nxt);
		}
		sort_arr.push_back(cur);
	}
	if (sort_arr.size() != n)
		cout << 0 << '\n';

	else {
		for (auto a : sort_arr)
			cout << a << '\n';
	}

	return 0;
}