BOJ 2623

05 Feb 2020 • ProblemSolving

음악프로그램

문제출처

문제 해석

  • 보조 PD들이 정해놓은 가수 출연 순서를 유배하지 않고, 전체 출연순서를 정하는 문제입니다.
  • 모두를 만족하는 순서를 정하지 못할 수도 있습니다.

설계(5)

  • 전형적인 위상정렬 문제입니다.
  • 모두를 만족하는 순서를 정하지 못하는 경우는 사이클이 존재한다는 의미이므로, 사이클이 생기는지 체크해야 합니다.
  • dfs 또는 큐로 구현할 수 있으며, 두개 다 구현해보았습니다.

구현(10)

코드1(dfs)
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 1000

vector<int> adj[MAXN];
bool visited[MAXN];
bool finished[MAXN];
int N, M;
int tmp_arr[MAXN];
vector<int> vt;
bool cycle = false;
void dfs(int now) {
	if (cycle) return;
	visited[now] = true;
	for (int i = 0; i < adj[now].size(); i++) {
		int next = adj[now][i];
		if (!visited[next]) {
			dfs(next);
		}
		else if (!finished[next]) {
			cycle = true;
		}
	}
	finished[now] = true;
	vt.push_back(now);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	while (M--){
		int num;
		cin >> num;
		for (int j= 0;j<num;j++){
			cin >> tmp_arr[j];
			tmp_arr[j]--;
		}
		for (int i = 0; i < num; i++) {
			for (int j = i + 1; j < num; j++) {
				adj[tmp_arr[i]].push_back(tmp_arr[j]);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		if (visited[i]) continue;
		dfs(i);
	}
	if (cycle) cout << "0\n";
	else {
		while (!vt.empty()) {
			cout << vt.back()+1 << "\n";
			vt.pop_back();
		}
	}
	return 0;
}
코드2(queue)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 1000

vector<int> adj[MAXN];
int N, M;
int tmp_arr[MAXN];
int indegree[MAXN];
vector<int> vt;
bool cycle = false;
queue<int> q;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	while (M--) {
		int num;
		cin >> num;
		for (int j = 0; j < num; j++) {
			cin >> tmp_arr[j];
			tmp_arr[j]--;
		}
		for (int i = 0; i < num; i++) {
			for (int j = i + 1; j < num; j++) {
				adj[tmp_arr[i]].push_back(tmp_arr[j]);
				indegree[tmp_arr[j]]++;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		if (indegree[i] == 0) q.push(i);
	}
	for (int i = 0; i < N; i++) {
		if (!q.size()) {
			cout << "0\n";
			return 0;
		}
		int now = q.front();
		q.pop();
		vt.push_back(now);
		for (int j = 0; j < adj[now].size(); j++) {
			int next = adj[now][j];
			if (--indegree[next] == 0) q.push(next);
		}
	}
	for (int i = 0; i < vt.size(); i++) {
		cout << vt[i] + 1 << "\n";
	}
	return 0;
}
디버깅
제출결과

0ms

마무리

  • 전형적인 위상정렬 문제로, 개념을 알면 어렵지 않게 풀 수 있습니다.
 BOJ

Related Posts