어흥
[백준 2623] 음악프로그램 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/2623
1. 주의할 점
- N과 M을 입력받은 다음, 각 보조PD가 정한 그룹수(Val), 그룹 순서가 차례대로 주어진다. 하지만 Val에 대한 어떠한 정보도 주어져 있지 않다. Val이 1인 경우 이후에 그룹이 1개만 나와서 순서에 의미가 없다. 이 경우 Vector에 추가하지 않도록 한다.
- 위상정렬 순서를 받을 때 어떤 방식으로 입력받고, 각 Vector에는 어떤 값을 저장할 것인지 잘 생각해야 한다.
2. 구현
- 각 Vector V[index]에는 바로 뒤에 올 index만 넣는다. 예를 들어 1 -> 4 -> 3의 순서를 지켜야 할 경우, V[1]에는 4만 추가하고 3은 V[4]에서 추가한다.
- 우선순위가 가장 높은(선행 그룹이 없는 경우) 그룹을 우선 Queue에 넣는다.
- 큐에서 뺀 그룹 뒤에 오는 그룹의 Conn 배열값을 1씩 감소시킨다. 해당 그룹의 Conn값이 0이 될 경우 큐에 넣는다.
- 순서를 정하지 못하는 경우는 선두에서 공연한 그룹이 다시 한번 공연해야 하는 경우로, Vector Ans에는 공연할 그룹 이 전부 담기지 않게 된다. 따라서, 최종적으로 Vector Ans의 크기가 전체 그룹의 수와 같지 않다면 0을 출력한다.
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int conn[1001];
vector<int> v[1001];
vector<int> ans;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int node, num, val, s, e;
cin >> node >> num;
queue<int> q;
for (int i = 0; i < num; i++) {
cin >> val;
if (val == 0) continue;
cin >> s;
if (val == 1) continue;
for (int j = 0; j < val - 1; j++) {
cin >> e;
v[s].push_back(e);
conn[e]++;
s = e;
}
}
for (int i = 1; i <= node; i++)
if (conn[i] == 0)
q.push(i);
while (!q.empty()) {
int cidx = q.front();
q.pop();
ans.push_back(cidx);
for (int i = 0; i < v[cidx].size(); i++) {
int next = v[cidx][i];
conn[next]--;
if (conn[next] == 0)
q.push(next);
}
}
if (ans.size() != node) cout << 0;
else {
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << '\n';
}
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 15685] 드래곤 커브 (C++) (0) | 2020.03.13 |
---|---|
[백준 1948] 임계경로 (C++) (0) | 2020.03.13 |
[백준 6118] 숨바꼭질 (C++) (0) | 2020.03.12 |
[백준 16179] 두 동전 (C++) (0) | 2020.03.11 |
[백준 11578] 팀원 모집 (C++) (0) | 2020.03.11 |
Comments