위상 정렬 (Topology Sort) 알고리즘
- Algorithm/Concept
- 2021. 12. 15.
위상 정렬 알고리즘
정렬 알고리즘의 일종이다. 위상 정렬이란, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다. 예시의 상황을 보자.
- 예시
자바 공부의 커리큘럼에는 순서가 있다.
1) JAVA
2) JSP
3) Spring
이때 우리는 각 과목을 노드로 표현하고, 'JAVA' -> 'JSP'로 이어질 수 있도록 방향성을 갖는 간선을 그릴 수 있다. 다시 말해 그래프 상에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다.
- 책에서의 예시
1) 자료구조
2) 알고리즘
3) 고급 알고리즘
위 3가지로 구성되어있는 과목 커리큘럼이 있다. '알고리즘'의 선수 과목으로 '자료구조'가 있고, '고급 알고리즘'의 선수 과목으로 '자료구조', '알고리즘'이 있다. 이 경우에는 '자료구조 -> 알고리즘 -> 고급 알고리즘'의 순서로 강의를 수강해야한다. 그래야 모든 과목 수강이 가능하다.
위상 정렬 알고리즘 구성
- 진입차수 (Indegree)
특정한 노드로 들어오는 간선의 개수
- 진출차수 (Outdegree)
특정한 노드에서 나가는 간선의 개수
1) 진입차수가 0인 노드를 큐에 넣는다.
2) 큐가 빌때까지 다음의 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
결과적으로, 각 노드가 큐에 들어온 순서와 위상 정렬을 수행한 결과와 같다.
위상 정렬 알고리즘의 동작 원리
- 사이클이 없는 방향 그래프다.
사이클이 존재하는 경우, 사이클에 포함되어있는 원소 중에서 어떠한 원소도 큐에 들어가지 못하기 때문에 이렇게 가정한다. 참고로 위상정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 더 많다.
1) 진입 차수가 0인 노드는 1번 노드이다.
2) 큐에서 노드 1을 꺼낸뒤, 노드 1에서 나가는 간선을 제거한다. 이때 진입차수가 0이되는 2번 노드, 5번 노드가 큐에 삽입된다.
3) 큐에서 노드 2를 꺼낸 후 나가는 간선을 제거한다. 이때 진입차수가 0이 되는 3번 노드가 큐에 삽입된다.
4) 큐에서 노드 5를 꺼낸 후 나가는 간선을 제거한다. 이때 진입차수가 0이 되는 6번 노드가 큐에 삽입된다.
5) 큐에서 노드 3를 꺼낸 후 나가는 간선을 제거한다. 이때 진입차수가 0이 되는 새로운 노드는 없다.
6) 큐에서 노드 6를 꺼낸 후 나가는 간선을 제거한다. 이때 진입차수가 0이 되는 4번 노드가 큐에 삽입된다.
7) 큐에서 노드 4를 꺼낸 후 나가는 간선을 제거한다. 이때 진입차수가 0이 되는 7번 노드가 큐에 삽입된다.
8) 큐에서 노드 7를 꺼낸 후 나가는 간선을 제거한다. 더이상 큐에 들어갈 노드는 없다.
9) 결과
위에서 각 노드가 큐에 들어온 순서와 위상 정렬을 수행한 결과와 같다고 했다. 결국 위상 정렬의 결과는 아래와 같다.
1 -> 2-> 5-> 3-> 6-> 4-> 7
코드 분석
1) 필요한 변수를 선언하고 입력받은 데이터를 각 변수에 셋팅한다.
indegree 배열이 진입차수를 담을 객체다. 큐에 들어간 노드를 꺼냈을때 해당 노드와 연결되어있는 간선이 제거되면 진입차수를 계산하여 해당 배열을 갱신해줘야한다.
package Y20_Graph;
import java.util.*;
public class TopologySort {
public static int v; // 노드의 개수(V)
public static int e; // 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
// 모든 노드에 대한 진입차수는 0으로 초기화
public static int[] indegree = new int[100001];
// 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// 위상 정렬 함수
public static void topologySort() {
...
}
/*
7 8
1 2
1 5
2 3
2 6
3 4
4 9
5 6
6 4
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 그래프 초기화
for (int i = 0; i <= v; i++) {
graph.add(new ArrayList<Integer>());
}
// 방향 그래프의 모든 간선 정보를 입력 받기
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
graph.get(a).add(b); // 정점 A에서 B로 이동 가능
// 진입 차수를 1 증가
indegree[b] += 1;
}
topologySort();
}
}
2) topologySort() 메서드를 분석해보자.
2-1) 결과를 담을 리스트 result와 큐 q 를 선언한다.
...
// 위상 정렬 함수
public static void topologySort() {
ArrayList<Integer> result = new ArrayList<>(); // 알고리즘 수행 결과를 담을 리스트
Queue<Integer> q = new LinkedList<>(); // 큐 라이브러리 사용
...
}
...
2-2) 진입차수가 0인 노드를 큐에 삽입한다.
...
// 위상 정렬 함수
public static void topologySort() {
ArrayList<Integer> result = new ArrayList<>(); // 알고리즘 수행 결과를 담을 리스트
Queue<Integer> q = new LinkedList<>(); // 큐 라이브러리 사용
// 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for (int i = 1; i <= v; i++) {
if (indegree[i] == 0) {
q.offer(i);
}
}
}
...
2-3) 큐가 빌때까지 반복한다.
반복문 안에서는 큐에서 원소를 꺼내고, 해당 원소와 연결된 노드들의 진입차수를 -1 한다.
(나가는 간선들을 제거하는 행위)
제거 후, 새롭게 0이 되는 노드를 큐에 삽입한다. 결과적으로 큐에 삽입된 순서인 result 리스트를 출력한다.
...
// 위상 정렬 함수
public static void topologySort() {
...
// 큐가 빌 때까지 반복
while (!q.isEmpty()) {
// 큐에서 원소 꺼내기
int now = q.poll();
result.add(now);
// 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for (int i = 0; i < graph.get(now).size(); i++) { // 연결된 노드만큼 반복
indegree[graph.get(now).get(i)] -= 1;
// 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if (indegree[graph.get(now).get(i)] == 0) {
q.offer(graph.get(now).get(i));
}
}
}
// 위상 정렬을 수행한 결과 출력
result.stream()
.map(integer -> integer + " ")
.forEach(System.out::print);
}
...
위상 정렬의 특징
1) 위상 정렬은 DAG(Direct Acyclic Graph) 인 순환하지 않는 방향 그래프의 경우에 가능하다.
2) 여러가지 답이 존재할 수 있다. 큐에 들어갈 노드(원소)가 여러개일 경우를 말한다.
3) 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단한다.
-> 따라서 while()문은 큐가 빌때까지 반복한다.
4) 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수 있다.
Reference
https://freedeveloper.tistory.com/390
'이것이 코딩테스트다' 교재 참고
'Algorithm > Concept' 카테고리의 다른 글
| 그리디 (Greedy) (0) | 2022.03.07 |
|---|---|
| binarySearch 이진탐색의 lowerBound, upperBound (중복 원소 중 첫번째 인덱스와 마지막 인덱스 구하기) (0) | 2021.12.26 |
| 최소 신장트리 알고리즘, 크루스칼 알고리즘 (Kruskal) (0) | 2021.12.15 |
| 서로소 집합 (Disjoint Sets) 알고리즘 (0) | 2021.12.15 |
| 최단경로 찾기 - 플로이드 워셜 알고리즘 (0) | 2021.12.08 |