위상 정렬
위상 정렬 (topology sort)
위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
| 기능 | 특징 | 시간 복잡도(노드 수 :V, 에지 수 :E) |
| 노드 간의 순서를 결정 | 사이클이 없어야 함 | O(V+E) |
(참고 : https://m.blog.naver.com/ndb796/221236874984)
위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.
위상 정렬의 핵심 이론
위상 정렬은 다음과 같은 단계로 설명할 수 있다. 다음 예를 보자.
위상 정렬의 원리 이해하기
1. 진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다. 다음을 보면 ArrayList로 그래프를 표현했다. 그래프는 사이클이 없는 상태이다.
진입 차수 배열 D를 다음과 같이 업데이트한다. 1에서 2, 3을 가리키고 있으므로 D[2], D[3]을 각각 1만큼 증가시키는 과정을 끝까지 한 결과 배열이다.
2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.
위 그림의 경우 진입 차수가 0인 노드 1을 선택하여 2, 3의 진입 차수를 1씩 빼 D[2], D[3]을 0으로 만든 것이다. 계속해서 다음 노드 2를 선택해 반복한다. 이 과정은 모든 노드가 정렬될 때까지 반복한다. 여기서 진입 차수가 0인 노드를 3을 먼저 선택했다면 3이 우선 위상 정렬 배열에 들어갈 것이다. 앞서 위상 정렬이 늘 같은 정렬 결과를 보장하지 않는다고 말했던 것이 바로 이런 경우를 말하는 것이다.
위상 정렬 배열 결과는 [1, 2, 3, 4, 5] 가 된다.
[백준 2252번] 줄 세우기
https://www.acmicpc.net/problem/2252
학생들을 노드로 생각하고, 키 순서 비교 데이터로 에지를 만든다고 생각했을 때 노드의 순서를 도출하는 가장 기본적인 문제이다. 특히 답이 여러 개일 때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일하다는 것을 알 수 있다.
1. 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열값을 업데이트한다.
2. 다음 순서에 따라 위상 정렬을 수행한다.
1. 진입 차수가 0인 노드를 큐에 저장한다.
2. 큐에서 데이터를 poll해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다.
3. 감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer한다.
4. 큐가 빌 때까지 1~3을 반복한다.
[정답]
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
ArrayList<ArrayList<Integer>> A = new ArrayList<>();
for (int i = 0; i <= N; i++) {
A.add(new ArrayList<>());
}
int[] indegree = new int[N + 1]; // 진입 차수 배열
for (int i = 0; i < M; i++) {
int S = sc.nextInt();
int E = sc.nextInt();
A.get(S).add(E);
indegree[E]++; // 진입차수 배열 데이터 저장하기
}
Queue<Integer> queue = new LinkedList<>(); // 위상 정렬 수행
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int now = queue.poll();
System.out.print(now + " ");
for (int next : A.get(now)) {
indegree[next]--;
if (indegree[next] == 0) {
queue.offer(next);
}
}
}
}
}
[원본]
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static ArrayList<Integer>[] A;
static int[] inDegree;
static int[] answer;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 학생 수 (노드)
M = Integer.parseInt(st.nextToken()); // 비교 횟수
A = new ArrayList[N + 1]; // 비교값 저장 (에지)
inDegree = new int[N + 1]; // 진입 차수 배열
answer = new int[N]; // 정답 배열
for (int i = 1; i <= N; i++) {
A[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
A[a].add(b);
inDegree[b]++;
}
topology();
for (int a : answer) {
System.out.print(a + " ");
}
}
static void topology() {
Queue<Integer> queue = new LinkedList<>();
int idx = 0;
for (int i = 1; i <= N; i++) {
if(inDegree[i] == 0){ // 진입 차수 0인 것들 queue에 넣고 정답 배열에 저장
queue.add(i);
answer[idx++] = i;
}
}
while (!queue.isEmpty()) {
int now = queue.poll();
for (int i : A[now]) { // 진입 차수 0인 노드가 가리키는 노드들 방문
if (--inDegree[i] == 0) { // 진입 차수 1씩 뺀 후 그 값이 0이라면
queue.add(i); // queue에 넣은 후 정답 배열에 저장
answer[idx++] = i;
}
}
}
}
}
[백준 1516번] 게임 개발하기
https://www.acmicpc.net/problem/1516
이 문제를 풀기 위해서는 어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 있을 수 있다라는 문장에 주목해야 한다. 각 건물을 노드라고 생각하면 그래프 형태에서 노드 순서를 정렬하는 알고리즘인 위상 정렬을 사용하는 문제라는 것을 눈치챌 수 있다. 건물의 수가 최대 500, 시간 복잡도가 2초이므로 시간 제한 부담은 거의 없다.
1. 인접 리스트로 그래프를 표현할 때는 (인접 노드, 건물 번호)를 Node로 선언하여 연결한다. 진입 차수 배열은 [0, 1, 1, 2, 1], 정답 배열은 모두 0으로 초기화한다.
2. 위상 정렬을 실행하면서 각 건물을 짓는 데 걸리는 최대 시간을 업데이트한다. 업데이트는 다음과 같은 방법으로 수행한다.
진입 차수 배열과 위상 정렬 배열, 정답 배열 업데이트 방법
Math.max(현재 건물(노드)에 저장된 최대 시간, 이전 건물(노드)에 저장된 최대 시간 + 현재 건물(노드)의 생산 시간)
3. 정답 배열에 자기 건물을 짓는 데 걸리는 시간을 더한 후 정답 배열을 차례대로 출력한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
ArrayList<ArrayList<Integer>> A = new ArrayList<>();
for (int i = 0; i <= N; i++) {
A.add(new ArrayList<>());
}
int[] indegree = new int[N + 1]; // 진입 차수 배열
int[] selfBuild = new int[N + 1]; // 자기 자신을 짓는데 걸리는 시간
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
selfBuild[i] = Integer.parseInt(st.nextToken()); // 건물을 짓는데 걸리는 시간
while (true) { // 인접 리스트 초기화하기
int preTemp = Integer.parseInt(st.nextToken());
if(preTemp == -1)
break;
A.get(preTemp).add(i);
indegree[i]++; // 진입 차수 배열 초기화하기
}
}
// 위상 정렬
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= N; i++) {
if(indegree[i] == 0) {
queue.offer(i);
}
}
int[] result = new int[N + 1];
while (!queue.isEmpty()) {
int now = queue.poll();
for (int next : A.get(now)) {
indegree[next]--;
// 시간 업데이트하기
result[next] = Math.max(result[next], result[now] + selfBuild[now]);
if(indegree[next] == 0)
queue.offer(next);
}
}
for (int i = 1; i <= N; i++) {
System.out.println(result[i] + selfBuild[i]);
}
}
}
시간 업데이트 하는 부분이 포인트다. 만약 1번 건물이 10시간, 2번 건물이 4시간, 3번 건물이 1시간이 걸리고 1번과 2번이 먼저 지어져야 한다고 했을 때, 3번 건물이 지어지는 시간은 11시간이 된다. 1번과 2번이 동시에 지어지며 2번은 4시간 만에 끝나지만 3번은 1번이 다 지어질 때까지 기다려야 하기 때문이다. 그래서 항상 더 큰 값을 넣는 것이다. 사실 저 논리적인 부분만 제외하곤 문제 유형은 거의 흡사하다. 저 한 문장을 생각해 낼 수 있느냐의 차이. 항상 알고리즘을 먼저 생각하고 코딩하기 시작하는 습관을 들이자.
[백준 1948번] 임계경로
https://www.acmicpc.net/problem/1948
출발 도시와 도착 도시가 주어지기 때문에 일반적인 위상 정렬이 아닌 시작점을 출발 도시로 지정하고 위상 정렬을 수행하면 출발 도시에서 도착 도시까지 거치는 모든 도시와 관련된 임계 경로값을 구할 수 있다. 단, 이 문제의 핵심은 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는 것인데, 이를 해결하려면 에지 뒤집기라는 아이디어가 필요하다. 에지 뒤집기 아이디어는 그래프 문제에서 종종 나오는 개념이므로 이 문제를 이용해 학습해 보자.
1. 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열 값을 업데이트한다. 이때 에지의 방향이 반대인 역방향 인접 리스트로 함께 생성하고 저장한다.
2. 시작 도시에서 위상 정렬을 수행해 각 도시와 관련된 임계 경로를 저장한다.
3. 도착 도시에서 역방향으로 위상 정렬을 수행한다. 이때 '이 도시의 임계 경로값 + 도로 시간(에지) == 이전 도시의 임계 경로값' 일 경우에는 이 도로를 1분도 쉬지 않고 달려야 하는 도로로 카운팅하고, 이 도시를 큐에 삽입하는 로직으로 구현해야 한다.
4. 도착 도시의 임계 경로값(12)과 1분도 쉬지 않고 달려야 하는 도로의 수(5)를 출력한다.
노드를 큐에 삽입할 때 주의할 점
1분도 쉬지 않고 달려야 하는 도로로 이어진 노드와 연결된 다른 도로만이 1분도 쉬지 않고 달려야 하는 도로의 후보가 될 수 있으므로 이 메커니즘을 바탕으로 노드를 큐에 삽입해야 한다. 또한 중복으로 도로를 카운트하지 않기 위해 이미 방문한 적이 있는 한 노드는 큐에 넣어 주지 않는다. 기존의 위상 정렬 방식을 완벽하게 이해하고, 요구사항에 따라 적절하게 로직을 수정할 수 있어야만 문제를 풀 수 있기 때문에 많이 고민해야 한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
static class Node {
int targetNode;
int value;
public Node(int targetNode, int value) {
this.targetNode = targetNode;
this.value = value;
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 도시 개수
int M = Integer.parseInt(br.readLine()); // 도로 개수
ArrayList<ArrayList<Node>> A = new ArrayList<>();
ArrayList<ArrayList<Node>> reverseA = new ArrayList<>();
for (int i = 0; i <= N; i++) {
A.add(new ArrayList<>());
reverseA.add(new ArrayList<>());
}
int[] indegree = new int[N + 1]; // 진입 차수 배열
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
A.get(S).add(new Node(E, V));
reverseA.get(E).add(new Node(S, V)); // 역방향 에지 정보 저장
indegree[E]++; // 진입 차수 배열 초기화
}
StringTokenizer st = new StringTokenizer(br.readLine());
int start_city = Integer.parseInt(st.nextToken());
int end_city = Integer.parseInt(st.nextToken());
// 위상 정렬
Queue<Integer> queue = new LinkedList<>();
queue.offer(start_city);
int[] result = new int[N + 1];
while (!queue.isEmpty()) {
int now = queue.poll();
for (Node next : A.get(now)) {
indegree[next.targetNode]--;
result[next.targetNode] = Math.max(result[next.targetNode], result[now] + next.value);
if(indegree[next.targetNode] == 0)
queue.offer(next.targetNode);
}
}
// 위상 정렬 reverse
int resultCount = 0;
boolean[] visited = new boolean[N + 1];
queue = new LinkedList<>();
queue.offer(end_city);
visited[end_city] = true;
while (!queue.isEmpty()) {
int now = queue.poll();
for (Node next : reverseA.get(now)) {
// 1분도 쉬지 않는 도로 체크하기
if (result[next.targetNode] + next.value == result[now]) {
resultCount++;
// 중복 카운트 방지를 위해 이미 방문한 적이 있는 노드 제외하기
if(visited[next.targetNode] == false) {
visited[next.targetNode] = true;
queue.offer(next.targetNode);
}
}
}
}
System.out.println(result[end_city]);
System.out.println(resultCount);
}
}
[참고 자료]
- Do it! 알고리즘 코딩 테스트 자바편