어흥

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

알고리즘/백준

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

라이언납시오 2020. 3. 12. 20:24
728x90
반응형

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

 

2623번: 음악프로그램

첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다.

www.acmicpc.net

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;
}
728x90
반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준 15685] 드래곤 커브 (C++)  (0) 2020.03.13
[백준 1948] 임계경로 (C++)  (0) 2020.03.13
[백준 6118] 숨바꼭질 (C++)  (0) 2020.03.12
[백준 16179] 두 동전 (C++)  (0) 2020.03.11
[백준 11578] 팀원 모집 (C++)  (0) 2020.03.11
Comments