백준 2252번 줄 세우기

KSM_alex·2023년 1월 22일
0

백준

목록 보기
3/9

링크텍스트

  • 풀이 방법
    Topological sort를 이용한다. 각 학생을 vertex로 보고, 각 규칙을 directed edge로 볼 수 있다. 결과는 규칙을 만족하는 결과를 요구하므로, 모든 edge의 방향성을 만족하는 topological sort가 적절하다.

  • Topological Sort
    Topological sort의 원리는 다음과 같다.

    1. SCC(Strongly connected component) detecting을 한다.

    SCC는 directed graph에서 모든 정점으로부터 다른 정점까지의 경로가 있는 정점의 집합을 의미한다. SCC 내에는 cycle이 있기 때문에, 모든 directed edge를 만족하는 순서에 따라 sort를 할 수 없다. 즉, SCC가 있는 경우에는 topological sort를 할 수 없다.

    2. DFS를 한다. DFS가 끝난 vertex는 queue에 push한다.

    DFS가 끝났다는 것은 자신보다 우선순위가 앞서는 모든 정점을 방문한 것이므로, queue에 push하면 자신보다 우선순위가 빠른 정점보다 뒤에 위치한다.

    3. Queue가 곧 결과가 된다.

    -- 참고) 어떤 vertex의 ancestor가 궁금하다면, (start time, finish time)을 기록해두는 방법을 이용할 수 있다. Vertex v1은 (s1, f1), vertex v2는 (s2, f2)이고 s1 < s2, f2 < f1이면 v1은 v2의 ancestor이다.

  • 시간복잡도
    모든 vertex에 대해 DFS를 수행하고 adjacency list를 사용하여 O(V + E)의 시간복잡도를 가진다.
    (V: # of vertices, E: # of edges)

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int n, m;

vector<int> graph[32001];
bool visited[32001];
deque<int> que;

void DFS(int n) {
	visited[n] = true;

	for (int i : graph[n]) {
		if (!visited[i]) {
			DFS(i);
		}
	}

	que.push_front(n);
}

void topologicalSort() {
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			DFS(i);
		}
	}
}

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

	int from, to;
	for (int i = 0; i < m; i++) {
		cin >> from >> to;
		graph[from].push_back(to);
	}

	topologicalSort();

	for (int i : que) {
		cout << i << " ";
	}

	cout << endl;

	return 0;
}

0개의 댓글