[BOJ/2623] 음악 프로그램, c++

www.acmicpc.net/problem/2623

2623번: 음악프로그램

한줄 후기 : 세상 어떤 pd가 위상정렬로 순서를 정해요

 

이건 읽자마자 위상정렬 같았음

//AC
//BOJ 2623 음악 프로그램
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> music[1010];
vector<int> ans;
int ind[1010];
int main(){
	int n, m;
	cin >> n >> m;
	for(int i=0; i<m; i++){
		int t, cur, prev; 
		scanf("%d", &t);
		for(int i=0; i<t; i++){
			scanf("%d", &cur);
			if(i==0){
				prev = cur;
			}
			else{
				music[prev].push_back(cur);
				ind[cur]++;
				prev = cur;
			}
		}
	}
	queue<int> q;
	for(int i=1; i<=n; i++){
		if(ind[i] == 0){
			q.push(i);
		}
	}
	for(int i=1; i<=n; i++){
		if(q.empty()){
			printf("0\n");
			return 0;
		}
		int x = q.front();
		q.pop();
		ans.push_back(x);
		for(int y : music[x]){
			ind[y]--;
			if(ind[y]==0){
				q.push(y);
			}
		}
	}
	for(int sing : ans){
		printf("%d\n", sing);
	}
	return 0;
}

진짜 그냥 그래프 위상정렬 처럼 풀면된다.

입력이 한줄로 들어오기 때문에 바로 앞 (prev) 랑 비교해서 그래프를 연결해줘야한다.

다른 피디의 순서는 상관 없다.

매번 ind가 0이 되는 가수를 큐에 넣고, 큐에 front 가수와 연결된 (front 가수 뒤에 오는 가수들) 가수들의 ind를 하나씩 줄여주며 반복하면된다.

만약 중간에 큐가 비어버리면 ind가 0인 가수가 없는 것(순서가 엉킴)

그러면 0을 출력하고 끝낸다.