[백준 2623] 음악프로그램 (C++)

문제 링크: https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

1. 주의할 점

- N과 M을 입력받은 다음, 각 보조PD가 정한 그룹수(Val), 그룹 순서가 차례대로 주어진다. 하지만 Val에 대한 어떠한 정보도 주어져 있지 않다. Val이 1인 경우 이후에 그룹이 1개만 나와서 순서에 의미가 없다. 이 경우 Vector에 추가하지 않도록 한다.

- 위상정렬 순서를 받을 때 어떤 방식으로 입력받고, 각 Vector에는 어떤 값을 저장할 것인지 잘 생각해야 한다.

 

2. 구현

- 각 Vector V[index]에는 바로 뒤에 올 index만 넣는다. 예를 들어 1 -> 4 -> 3의 순서를 지켜야 할 경우, V[1]에는 4만 추가하고 3은 V[4]에서 추가한다.

- 우선순위가 가장 높은(선행 그룹이 없는 경우) 그룹을 우선 Queue에 넣는다.

- 큐에서 뺀 그룹 뒤에 오는 그룹의 Conn 배열값을 1씩 감소시킨다. 해당 그룹의 Conn값이 0이 될 경우 큐에 넣는다.

- 순서를 정하지 못하는 경우는 선두에서 공연한 그룹이 다시 한번 공연해야 하는 경우로, Vector Ans에는 공연할 그룹    이 전부 담기지 않게 된다. 따라서, 최종적으로 Vector Ans의 크기가 전체 그룹의 수와 같지 않다면 0을 출력한다. 

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int conn[1001];
vector<int> v[1001];
vector<int> ans;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int node, num, val, s, e;
	cin >> node >> num;
	queue<int> q;
	for (int i = 0; i < num; i++) {
		cin >> val;
		if (val == 0) continue;
		cin >> s;
		if (val == 1) continue;
		for (int j = 0; j < val - 1; j++) {
			cin >> e;
			v[s].push_back(e);
			conn[e]++;
			s = e;
		}
	}
	for (int i = 1; i <= node; i++) 
		if (conn[i] == 0) 
			q.push(i);	
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		ans.push_back(cidx);
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i];
			conn[next]--;
			if (conn[next] == 0) 
				q.push(next);			
		}
	}
	if (ans.size() != node) cout << 0;
	else {
		for (int i = 0; i < ans.size(); i++)
			cout << ans[i] << '\n';
	}	
	system("pause");
	return 0;
}