위상 정렬이란?
위상 정렬이란 방향이 있는 비순환 그래프(DAG, Directed Acyclic Graph)에서 모든 노드를 방향성에 따라 순서대로 정렬하는 알고리즘이다. 즉, 모든 노드들을 자신을 가리키는 화살표가 있는 다른 노드보다 앞에 오도록 배열하는 것이다. 이 알고리즘은 그래프 내부의 우선순위가 있는 작업들을 수행하는 순서를 결정하기 위해 사용된다.
위상 정렬 알고리즘의 핵심은 진입 차수(in-degree)를 이용하는 것이다. 진입 차수는 어떤 노드로 들어오는 화살표의 수를 의미한다. 위상 정렬은 진입 차수가 0인 노드부터 처리하면서, 해당 노드에서 출발하는 모든 화살표를 제거하고, 그 화살표를 제거한 노드의 진입차수를 감소시킨다. 이러한 과정을 반복하여 모든 노드를 처리하는 순서를 구한다.
위상 정렬의 시간 복잡도는 노드의 수와 간선의 수에 따라 달라지며, O(|V|+|E|)의 시간 복잡도를 가지는데, 여기서 |V|는 노드의 수, |E|는 간선의 수를 의미한다.
※위상 정렬의 단계
1. 각 노드의 진입 차수를 계산한다.
2. 진입 차수가 0인 노드를 큐에 추가한다.
3. 큐에서 노드를 하나씩 꺼내면서, 해당 노드에서 출발하는 모든 간선을 제거한다. 이때, 해당 노드로 들어오는 간선이 제거됨에 따라 다른 노드들의 진입 차수가 감소할 수 있으므로, 진입 차수를 감소시키면서 큐에 추가한다.
4. 큐가 빌 때까지 3번의 과정을 반복합니다.
예시 - 2252번: 줄 세우기 - Kotlin
2252번: 줄 세우기 - Kotlin (위상 정렬)
2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞
everyday-develop-myself.tistory.com
'개발자의 기본 소양 > ALGORITHM' 카테고리의 다른 글
| 누적합(부분합)을 응용해서 문제 해결하기 by Kotlin (1) | 2023.10.09 |
|---|---|
| Euclidean algorithm (유클리드 호제법) (0) | 2023.03.03 |
| Knapsack Problem (배낭 문제) with 12865번: 평범한 배낭 (0) | 2023.02.26 |
| BackTracking with 9663번: N-Queen (0) | 2023.02.24 |
| Floyd-Warshall Algirithm (플로이드 워셜 알고리즘) (0) | 2023.02.23 |
