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

문제 링크입니다! https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

문제 조건

출력 예시

1번 PD의 경우 1번 -> 4번 -> 3번

2번 PD의 경우 6번 -> 2번 -> 2번 -> 5번 -> 4번

3번 PD의 경우 2번 -> 3번 순으로 공연을 맡습니다.

1번을 방송하기 위해서는 선행이 없음으로 바로 방송할 수 있습니다.

2번의 경우는 6번을 먼저 방송 후 방송해야 합니다.

3번의 경우는 4번과 2번을 먼저 방송해야 합니다.

따라서 X번 -> Y번 일때, X vector에 Y의 값을 저장 후, X -> Y 탐색을 통해서 방송 순서를 찾아가면 됩니다.

처음 방송 순서는 선행 방송이 아무도 없는 경우 즉, connect 배열의 값이 0인 X번 부터 탐색을 시작합니다.

X와 연결된 Y번을 확인 후,  Y번의 connect 값을 -1 해줍니다. 이때 connect 값이 0이 되었다면, 선행 방송을 모두 했다는 의미임으로 queue에 넣어준 뒤 탐색을 이어갑니다.

 

문제 접근 방법

1. X번에 Y값을 넣어줍니다.

2. connect의 값이 0인 지점을 찾아서 queue에 넣어줍니다.

3. 탐색을 통해서 다음 순서를 확인한 뒤, connect의 값이 0이라면 queue에 넣어줍니다.

4. 순서가 N개 만큼 저장되어 있다면 순서를 출력해주고, N개 미만으로 저장되어 있다면 0을 출력해줍니다.

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int N, M;
vector<int> order[101];
vector<int> Next[1001];
vector<int> ans;
int connect[1001];
int check[1001];
queue<int> q;

void bfs() {
	while (!q.empty()) {
		int x = q.front();
		ans.push_back(x);
		q.pop();
		for (int i = 0; i < Next[x].size(); i++) {
			int xx = Next[x][i];
			connect[xx]--;
			if (connect[xx] == 0) {
				q.push(xx);
			}
		}
	}
}

void solve() {
	for (int i = 1; i <= N; i++) {
		if (connect[i] == 0) {
			q.push(i);
		}
	}
	bfs();
	if (ans.size() == N) {
		for (int i = 0; i < ans.size(); i++) {
			cout << ans[i] << "\n";
		}
	}
	else cout << "0";
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int num;
		cin >> num;
		for (int j = 0; j < num; j++) {
			int x;
			cin >> x;
			order[i].push_back(x);
		}
	}
	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < order[i].size() - 1; j++) {
			int x = order[i][j];
			int y = order[i][j + 1];
			Next[x].push_back(y);
			connect[y]++;
		}
	}
	solve();
	return 0;
}