백준 2623번 음악프로그램

백준 2623번 음악프로그램

순서를 정하는 문제에서 바로 topological sort라는 느낌이 왔다.

SCC (Strongly Connected Component)

Directed graph의 component 중 각 node로부터 다른 모든 node로 이동하는 경로가 있는 component를 SCC라 한다. Cycle이 있는 경우, cycle의 경로에 포함되는 node들의 집합을 SCC라 할 수 있다.

SCC를 찾아내는 알고리즘에는 크게 세가지가 있다.
1. Tarjan's algorithm
2. Path-based algorithm
3. Kosaraju's algorithm

이번 문제는 topological sort를 위해 SCC detection만 수행하면 되므로, 단순하게 dfs를 통해 cycle이 존재하는지만 확인하였다.

Topological Sort

SCC(Strongly Connected Component)가 없는 directed graph에서 모든 edge의 방향성을 만족하도록 정렬하는 것을 말한다. Dfs를 통해 해결할 수 있다.

1. SCC detection을 수행한다. SCC가 존재한다면 그대로 종료한다.
2. DFS를 진행한다. DFS가 종료된 vertex는 queue에 push한다.
3. Queue가 결과값이 된다.
4. 만약 vertex간의 ancestor-descendant 관계를 파악하고 싶다면 dfs의 (start time, finish time)을 기록한다. DFS에서 ancestor-descendant 관계를 파악하는 기초적인 방법이다. 어떤 vertex v의 (start, finish) 가 다른 vertex u의 (start, finish)를 포함한다면, v는 u의 ancestor이다.

문제 풀이

Cycle detection을 먼저 수행한 후 topological sort를 수행해도 되지만, 시간복잡도와 코드의 간편성을 위해 동시에 수행한다.

정렬에 성공하는 경우 시간복잡도는 O(|V| + |E|)로 두가지 방법이 동일하지만, 정렬에 실패하는 경우 중간에 멈출 수 있기 때문에 동시에 수행하는 것이 이득이다. (아주 미미하지만)

Cycle detect를 위해 visited 배열을 bool이 아니라 int 형으로 선언한다. 0은 방문하지 않은 상태, 1은 dfs를 시작했지만 완료되지는 않은 상태, 즉 descendant에 대해 dfs를 진행하고 있는 상태, 2는 dfs가 종료된 상태를 의미한다. 만약 어떤 node가 dfs를 진행하다가 진행해야 하는 다음 node의 visited[] 값이 1이면 cycle이 존재하는 것이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <deque>
#include <set>

using namespace std;

int n, m;
vector<int> graph[1001];
deque<int> queue;
int visited[1001];
set<int> tmpSet[1001];

bool dfs(int v) {
	visited[v] = 1;

	for (int next : graph[v]) {
		if (!visited[next]) {
			if (dfs(next)) {
				return true;
			}
		}
		else if (visited[next] == 1) {
			return true;
		}
	}

	visited[v] = 2;

	queue.push_front(v);

	return false;
}

/* with SCC detecting */
bool topologicalSort() {
	memset(visited, 0, sizeof(visited));

	int cntComponent = 1;

	for (int v = 1; v <= n; v++) {
		if (!visited[v]) {
			if (dfs(v)) {
				return true;
			}
		}
	}

	return false;
}

int main(void) {
	cin >> n >> m;

	int cnt, from, to;
	
	for (int i = 0; i < m; i++) {
		cin >> cnt;
		cin >> from;
		for (int j = 1; j < cnt; j++) {
			cin >> to;
			tmpSet[from].insert(to);
			from = to;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int v : tmpSet[i]) {
			graph[i].push_back(v);
		}
	}

	if (topologicalSort()) {
		cout << 0 << endl;
	}
	else {
		for (int i : queue) {
			cout << i << endl;
		}
	}

	return 0;
}