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

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

2623번: 음악프로그램

[문제요약]
1~6까지 나열된 수열이 몇개 있다. 
ex)
- 1 4 3
- 6 2 5 4
- 2 3 
 
각 수열에 있는 숫자들의 순서는 지켜져야 한다. 하지만 중간에 다른 숫자가 들어와도 된다. 일렬로.
 
[문제 풀이]
처음에 문제를 읽으면서
1) 완탐은 안됨
2) DFS?
3) Union-find?
 
이렇게 3가지를 생각했는데... 3번 Union-find는 순서를 정할 수 없기 떄문에 안되니까. 보내고. 
DFS만 남았는데 도무지 DFS로는 방법이 떠오르지 않았다.... 
 
그래서 분류표를 열어 보니까 

위상 정렬이라는 걸 알 수 있었다. 예전에 본 적 있는것 같기도 한데.. 처음 들어봐서 위상 정렬을 한 번 찾아 보니, 
각 숫자의 "순서"를 매기고 그거에 맞게 queue에 넣어서.. 뽑아내는 그런거임.. 
 
근데 위상 정렬을 봐도 아이디어가 잘 생각이 안났다. 그래서 써칭을 좀 했음 ㅎ;;
 
[코드 구현]
 
1. 일단 위상 정렬을 진행한다. 근데 여기서, 순서를 매기는 방식이 내 앞에 오는 수의 숫자가 몇개인가? 이다. 
2. 1번을 구현하기 위해 입력 단에서,
    1) 내 뒤에 와야 하는 모든 수들을 vector에 넣어 둔다. 
    2) 앞에 오는 수의 개수를 priority에 담는다. -> 위상 정렬의 queue에 담을 우선순위로 사용된다. 

 
3. 일단 priority가 0인 값들을 q에 담고, 위에서부터 차례대로 탐색하면서 내 뒤에 오는 모든 숫자들의 priority값을 -1
     -> 이 과정에서 0이 되는 값은 q에 담는다. 

 
 
 

#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

int N,M; 
int priority[1002];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	int T;
	vector<int> v[1002];

	fill(priority, priority + 1002, 0);

	for (int i = 0; i < M; i++) {
		cin >> T;
		vector<int> test;
		int p;
		// 입력 받고, 저장
		for (int j = 0; j < T;j++) {
			cin >> p;
			test.push_back(p);
		}
		for (int j = 0; j < T; j++) {
			for (int k = j + 1; k < T; k++) {
				v[test[j]].push_back(test[k]);
				priority[test[k]]++;
			}
		}
	}

	queue<int> q;

	for (int i = 1; i <= N; i++) {
		if (!priority[i]) q.push(i);
	}

	vector<int> ans;

	while (!q.empty()) {
		int now = q.front();
		ans.push_back(now);
		q.pop();
		for (int i = 0; i < v[now].size();i++) {
			priority[v[now][i]]--;
			if (priority[v[now][i]] == 0) q.push(v[now][i]);
		}
	}

	if (ans.size() == N) {
		for (int i = 0; i < ans.size(); i++)
			cout << ans[i]<<'\n';
	}
	else
		cout << 0;

}

 
 
이제 너무 알고리즘만 생각해서... 모르는 알고리즘은 못 푸는 현상이 발발했는데 ㅠ...
예전같았으면 그냥 머리 쥐어짜내서 풀었을 것 같다.. 아쉽..
https://velog.io/@kimdukbae/%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-Topological-Sorting

[알고리즘] 위상 정렬 (Topological Sorting)