[G3] 백준 2623번 음악프로그램 C++ 위상 정렬

리뷰

 

가수의 출연 순서를 구하는 위상 정렬 문제, 보조PD 라는 것에 의미를 부여하는 함정에 빠지면 안된다.

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

 

문제 풀이

1. 가수의 개수n, 보조 PD의 개수m, 인접리스트용 벡터 path를 전역변수로 설정해 준다.
2. n과 m값을 입력 받고, m크기만큼의 루프를 돌려준다, 이후 가수의 개수 a와 가수 b를 입력 받아준다.
3. 가수의 개수를 전위 감소 연산을 통해 while루프를 돌려주고 그 이후의 가수 c를 입력 받아준다.
4. b의 path에 c를 push_back을 해준 뒤 b를 c로 교체시켜 준다. 이후 계속 반복해 준다.
5. 위 작업을 통해 가수의 순서대로 우선 순위가 적용되어 가수간의 출연 순서가 만들어 진다.
6. cnt벡터를 n + 1크기로, 값은 모두 0으로 초기화를 진행해 주고, 정답을 저장할 result 벡터도 초기화 해준다.
7. 1~n까지의 가수를 순회하며 각 가수의 인접 리스트에 존재하는 가수들의 cnt를 증가시켜 준다.
8. 정수형 큐 q를 초기화 해주고, cnt가 0인 가수를 큐에 모두 넣어준다.
9. 큐가 빌때까지 whle루프를 돌며, 큐에서 pop한 가수는 result에 push_back 해준다.
10. 이후 해당 가수의 인접리스트를 순회하며 해당 가수들의 cnt를 감소시켜 준다.
11. 만약 cnt를 감소시킨 결과 cnt가 0이 된 가수가 존재한다면 해당 가수도 큐에 추가해 준다.
12. 모든 작업을 마치고 난 후 result벡터에 저장된 가수의 수가 n과 동일하지 않다면 0을 출력한다.
13. 만약 동일하다면 result 벡터 내에 저장된 가수들을 줄바꿈을 기준으로 순서대로 출력해 주면 된다.

 

 

참고 사항

result의 size와 n이 다르다는 것은 사이클이 발생했거나 모든 가수가 출연하지 못하는 경우이다.

보조PD는 그저 우선 순위를 입력받기 위한 수단일 뿐 의미가 없다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;
int n, m;
vector<int> path[1001];

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

	cin >> n >> m;
	while (m--) {
		int a, b; cin >> a >> b;
		while (--a) {
			int c; cin >> c;
			path[b].push_back(c);
			b = c;
		}
	}

	vector<int> cnt(n + 1, 0);
	vector<int> result;
	for (int i = 1; i <= n; i++) {
		for (int j : path[i]) cnt[j]++;
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (!cnt[i]) q.push(i);
	}

	while (!q.empty()) {
		int cn = q.front(); q.pop();
		result.push_back(cn);
		for (int nn : path[cn]) {
			if (--cnt[nn] == 0) q.push(nn);
		}
	}

	if (result.size() != n) cout << 0;
	else for (int i : result) cout << i << "\n";
}