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

 

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

 

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

2623번: 음악프로그램

---

 

 

해결전략

 

위상 정렬  Topology Sort 

---

 

 

정답코드

 

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

int n, m; 		// n: 가수의 수, m: 보조 PD의 수
vector<int> v;  // 각 가수의 진입차수 저장 벡터
vector<vector<int>> graph; // 가수들의 순서 관계를 나타내는 그래프

bool isCycle = false; // 사이클 존재 여부를 체크하는 변수
vector<int> answer;   // 출연 순서를 저장할 벡터

void TopologySort()
{
	queue<int> Q; // 진입차수가 0인 노드를 담을 큐

	for(int i = 1; i <= n; i++){
		if(v[i] == 0){ // 진입차수가 0인 가수를 큐에 삽입
			Q.push(i);
		}
	}

	for (int i = 0; i < n; i++)
	{
		if(Q.empty()){ // 큐가 비어있다면 순서를 정할 수 없음을 의미(사이클 존재)
			isCycle = true;
			return;
		}

		int cur = Q.front(); // 현재 가수
		Q.pop();
		answer.push_back(cur); // 출연 순서에 추가

		for(int j = 0; j < graph[cur].size(); j++)
		{
			int next = graph[cur][j]; // 다음 가수
			v[next]--; 				  // 다음 가수의 진입차수 감소

			if(v[next] == 0){ // 진입차수가 0이 되면 큐에 추가
				Q.push(next);
			}
		}
	}
}

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

	cin >> n >> m;
	v.resize(n + 1); 
	graph.resize(n + 1); 

	int k; // 보조 PD가 담당한 가수의 수
	for(int i = 0; i < m; i++)
	{
		cin >> k;
		if (k == 0) continue;

		int prev, cur;
		cin >> prev;
		for(int j = 0; j < k-1; j++)
		{
			cin >> cur;

			graph[prev].push_back(cur); // 가수 순서 관계 그래프에 추가
			v[cur]++; // 진입차수 증가

			prev = cur;
		}		
	}

	TopologySort(); // 위상 정렬 실행

	if (isCycle) cout << "0"; // 사이클이 존재하면 0 출력
	else {
		for (int i = 0; i < answer.size(); i++){ // 사이클이 존재하지 않으면 순서대로 출력
			cout << answer[i] << "\n";
		}
	}

	return 0;
}

 

 

---

 

 

위상정렬 이론 참고

 

https://m42-orion.tistory.com/65

[C++ Algorithm] Graph - Topology Sort (위상 정렬)

 

 

---