최소 스패닝 트리(Minimum Spanning Tree) - 서로소 집합 자료구조, 크루스칼 알고리즘
이 글을 보기 전에 다음 문제를 한 번 풀어보는걸 추천한다(포스팅을 하게 된 이유)
https://www.acmicpc.net/problem/1197
직접 문제를 풀어 보면, 메모리 제한이 128MB이기 때문에 생각보다 까다로울 수 있다. 정점의 개수도 10,000개라서 섣불리 인접 행렬을 사용했다가는 입구부터 막힐 수 있다. 특히나 이 글에 대한 내용을 잘 모르면, 사이클을 탐색하는 과정에서 DFS로 접근하다가 매모리 초과를 수 없이 겪을 수 있다(경험담).
서로소 집합 자료 구조(Union-Find)
최소 스패닝 트리를 알아보기 전에 먼저 서로소 집합 자료 구조에 대해 알아야 한다.
서로소 집합 자료 구조란 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조
우리가 알고 있는 수학의 서로소와 같은 개념인데 조금 다른 점은, 원소들이 대표하는 값을 각각 가지고 있고, 이 대표하는 값이 같은 원소들이 집합을 이룬다. 만약 대표하는 값이 다르면 서로 다른 집합이 된다. 이를 트리 구조로 이해하면 더 쉽다.
각 노드는 자신의 부모 노드를 가지게 되는데, 이 부모 노드의 값이 자신을 대표하는 값이 된다. 여기서 부모 노드는 트리 구조처럼 부모 노드의 부모 노드가 있을 수 있으며 결국 루트 노드가 그 집합을 대표하는 값이 된다. 이 루트 값이 서로 다르면 서로소 관계가 되는 것이다.
- 자신을 대표하는 값 = 부모 노드
- 집합을 대표하는 값 = 루트 노드
- 같은 집합 관계 = 부모 노드가 같음 = 루트 노드가 같음 = 하나의 트리 구조
- 서로소 집합 관계 = 부모 노드가 다름 = 루트 노드가 다름 = 서로 다른 트리 구조
예시를 들어 보겠다.
| 노드 | 1 | 2 | 3 |
| 부모 | 1 | 1 | 2 |
위 트리에서 노드 3의 부모 노드는 2지만 2의 부모 노드가 1이므로 결국 3은 노드 1, 2와 같은 집합에 속하게 된다.
- 노드 3의 부모 노드 → 노드 2의 부모 노드 → 노드 1
위 두 트리는 각각 루트 값이 1과 5로 다르기 때문에 서로소 집합 관계다.
이 자료 구조에는 Union과 Find라는 대표적인 2가지 연산이 있다. 그래서 Union-Find 자료 구조라고도 한다.
Union - Find 연산
먼저 find 연산은 특정 원소가 속한 집합을 찾는 연산으로 자신의 부모 노드를 재귀적으로 찾다가 결국은 각 집합의 대표자(루트)를 반환하게 된다. 이 메서드를 호출하면 두 원소가 같은 집합에 속해 있는지 알 수 있다.
class Main {
private static int[] parents;
public static void main(String[] args) {
int v = 10;
parents = new int[v + 1];
// 자신의 노드 번호를 인덱스로 가지는 배열에 자기 자신을 부모 노드로 초기화
for (int i = 1; i <= v; i++) {
parents[i] = i;
}
}
private int find(int v) {
// 자기 자신을 부모로 하는, 루트 노드이면 반환
if (parents[v] == v) {
return v;
} else {
return findParent(parents[v]); // 재귀 호출로 루트 노드를 반환
}
}
// ...
}자바 코드로 구현된 메서드를 보면, 노드 번호를 인덱스로 가지는 parents 배열을 하나 선언한 뒤, 자기 자신을 부모 노드로 초기화 하고 있다. 이 의미는 만약 v = 10이라면 총 10개의 트리가 만들어 지고, 각각 자기 자신이 루트 노드가 된다는 의미다.
다음으로 union 연산은 두 개의 집합을 하나로 합치는 연산으로 한쪽의 루트를 다른 집합의 루트로 연결한다. 즉, 이전에는 서로 루트가 다른 2개의 트리였는데, 한쪽의 루트 노드가 다른 쪽의 루트 노드를 부모 노드로 연결하겠다는 것이다.
private void union(int v1, int v2) {
int v1Parent = find(v1); // 여기서 사실은 재귀 호출되어 루트 값을 반환
int v2Parent = find(v2);
if (v1Parent > v2Parent) {
parents[v1Parent] = v2Parent;
} else {
parents[v2Parent] = v1Parent;
}
}원소 v1과 v2의 부모(루트) 값을 find() 메서드로 찾은 뒤, 상대적으로 값이 큰 루트 노드가 낮은 값의 루트 노드를 부모로 삼는다. (사실 이 부분은 구현에 따라 바꿔주면 된다.
find : 특정 원소의 부모(루트)를 찾는 연산
union : 서로 다른 집합(트리)을 합치기 위해 한쪽 루트를 다른 쪽 루트로 연결하는 연산
이제 다시 예를 들어 보자. 총 5개의 노드가 있고, 초기화를 했다.
| 노드 | 1 | 2 | 3 | 4 | 5 |
| 부모 | 1 | 2 | 3 | 4 | 5 |
이를 처음 들었던 예시의 그래프처럼 만들어 보자. 그럼 먼저 1번 노드와 2번 노드를 Union 메서드로 합쳐야 한다.
| 노드 | 1 | 2 | 3 | 4 | 5 |
| 부모 | 1 | 1 | 3 | 4 | 5 |
그 다음 2번 노드와 3번 노드에 대해서도 Union 메서드를 호출한다.
| 노드 | 1 | 2 | 3 | 4 | 5 |
| 부모 | 1 | 1 | 1 | 4 | 5 |
노드 3의 부모(루트) 노드 값보다 노드 2의 부모(루트) 노드 값이 더 작기 때문에 노드 3의 부모 노드 값을 1로 바꿔 주면서 합쳤다.
이제 노드 4와 5도 합쳐보자.
| 노드 | 1 | 2 | 3 | 4 | 5 |
| 부모 | 1 | 1 | 1 | 4 | 4 |
이를 그래프로 나타내면 아래 그림과 같다.
그럼 마지막으로 두 그래프도 합쳐 보자. 여기서는 노드 3과 노드 4에 대해서 Union 메서드를 호출해 보겠다.
| 노드 | 1 | 2 | 3 | 4 | 5 |
| 부모 | 1 | 1 | 1 | 1 | 4 |
위 그래프에서 처럼 노드 5의 부모는 노드 4지만, 노드 4의 부모가 노드 1이므로 결국 위 노드들은 다 같은 집합(트리)이 된다.
그런데, 문제점이 하나 있다. 만약 위와 같은 트리가 아닌 한 쪽으로 편향된 트리가 만들어 졌다고 생각해 보자. 실제로 union 메서드를 호출하는 순서가 아래와 같으면 편향된 트리가 만들어 진다.
union(4, 5): 5 → 4union(3, 4): 5 → 4 → 3union(2, 3): 5 → 4 → 3 → 2union(1, 2): 5 → 4 → 3 → 2 → 1
| 노드 | 1 | 2 | 3 | 4 | 5 |
| 부모 | 1 | 1 | 2 | 3 | 4 |
이렇게 되면 노드 5번의 부모(루트)를 찾기 위해 find 메서드를 호출할 때 총 5번의 재귀 호출이 발생하게 된다. 즉, 최악의 경우 O(n)이 된다. 이를 개선하는 방법이 있다.
경로 압축(path compression)
방법은 아주 간단한데, 각 노드가 부모 노드를 저장하는 것이 아닌 루트 노드를 저장할 수 있게 find 메서드를 수정하면 된다.
private int find(int v) {
if (parents[v] == v) {
return v;
} else {
parents[v] = findParent(parents[v]); // 추가
return parents[v];
}
}위와 같이 부모 노드의 부모 노드를 저장한 뒤 반환하도록 코드를 추가해 주면 된다. 그러면 재귀 호출이 끝날 때 루트 노드가 각 노드의 부모 노드로 저장된다. 그 결과 위 예시처럼 편향되도록 메서드를 호출해도, 하나의 집합(트리)에 포함되어 있으면 모두 같은 부모를 바라보고 있게 된다.
| 노드 | 1 | 2 | 3 | 4 | 5 |
| 부모 | 1 | 1 | 1 | 1 | 1 |
이렇게 되면 같은 집합 내 어떤 노드를 호출하더라도 상수 시간의 O(1) 시간 복잡도를 가지게 된다.
사이클 판별
서로소 집합 자료구조는 무방향 그래프 내에서 사이클을 판별할 때 유용하게 사용할 수 있다. 알고리즘은 다음과 같다.
- 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 찾는다.
- 루트 노드가 다르면 두 노드를
union연산으로 합친다. - 루트 노드가 같다면 사이클이 발생한 것이다.
- 루트 노드가 다르면 두 노드를
- 모든 간선에 대해서 1번을 반복한다.
예를 들어 다음과 같은 그래프가 있을 때 사이클을 판별해 보겠다.
먼저 각 노드에 대해 자신을 부모 노드로 설정하도록 초기화 해준다. 이 상태는 각 노드가 모두 서로소 집합 관계다.
| 노드 | 1 | 2 | 3 | 4 |
| 부모 | 1 | 2 | 3 | 4 |
이제 간선의 순서대로 위 알고리즘을 그대로 실행해 보겠다.
- 간선 (1, 2)
노드 1의 부모와 노드 2의 부모는 서로 다르므로 union 연산을 실행해 합친다. 이때 노드 2의 부모가 노드 1의 부모보다 크므로 노드 1의 부모 값으로 바꿔 준다.
| 노드 | 1 | 2 | 3 | 4 |
| 부모 | 1 | 1 | 3 | 4 |
- 간선 (2, 3)
역시 부모가 다르므로 두 노드에 대해 union 연산을 수행한다. 역시 노드 3의 부모가 노드 2의 부모보다 크기 때문에 노드 2의 부모로 값을 바꿔 준다. 결국 노드 1, 2, 3은 같은 부모(루트)를 가지게 되는 집합이 된다.
| 노드 | 1 | 2 | 3 | 4 |
| 부모 | 1 | 1 | 1 | 4 |
- 간선 (2, 4)
역시 과정은 같으므로 결과만 보겠다.
| 노드 | 1 | 2 | 3 | 4 |
| 부모 | 1 | 1 | 1 | 1 |
- 간선 (3, 4)
쉽게 예상이 되겠지만, 노드 3과 노드 4의 부모는 같으므로 사이클이 발생했다고 판별할 수 있다. 만약 (1, 2)를 제외한 나머지 3개의 간선 중, 1개만 없었더라도 사이클은 발생하지 않았을 것이다. 직접 간선을 없애고 알고리즘을 따라가다 보면, 같은 부모를 가진 두 노드를 연결하는 간선은 없다.
최소 스패닝 트리(최소 신장 트리)
먼저 최소 스패닝 트리(또는 최소 신장 트리)에 대해 알기 전에 스패닝(신장) 트리가 무엇인지 알아야 한다.
스패닝 트리(Spanning Tree) : 한 그래프의 모든 노드를 포함하면서 사이클이 없는 부분 그래프
스패닝 트리의 정의에서 중요한 2가지 조건이 있다.
- 모든 노드를 포함해야 한다.
- 사이클이 없어야 한다.
위 그래프에서 스패닝 트리를 찾아보면 다음과 같이 3개가 나온다.
예시에서도 알 수 있듯이, 위 두 조건을 만족하기 위해서는 간선의 개수가 항상 (노드의 개수 - 1)개여야 한다. 사실 위 조건은 트리(Tree) 구조의 조건과 동일하다. 하지만 트리와 다른 점은 스패닝 트리를 트리가 아닌 무방향 그래프에서 찾아 내야한다는 것이다. 그리고 이를 찾는 방법은 앞서 봤던 서로소 집합 자료 구조를 이용하는 것이다. 알고리즘은 다음과 같다.
- 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 찾는다.
- 루트 노드가 다르면 두 노드를
union연산으로 합친 후 간선을 스패닝 트리 집합에 넣는다. - 루트 노드가 같다면 사이클이 발생한 것이므로 패스하다.
- 루트 노드가 다르면 두 노드를
- 스패닝 트리 집합의 간선 개수가 (노드의 개수 -1)개일 때까지 반복한다.
사실 사이클을 찾는 알고리즘과 반복 횟수만 다를 뿐, 매우 유사하다.
만약 위 그래프의 각 간선에 가중치가 추가되는 가중치 무방향 그래프에서 최소 가중치 간선들만으로 스패닝 트리를 구성한 것이 최소 스패닝 트리다. 스패닝 트리를 만드는데 최소 비용이 들어간다고 해서 우리나라 말로 최소 비용 신장 트리라고도 한다.
최소 스패닝 트리(Minimum Spanning Tree) : 스패닝 트리들 중에서 그 가중치의 합이 최소인 트리
이 MST를 구하는 것은 사실 실생활에서 중요한 문제다. 우리에게 친숙한 네트워크 연결을 생각해 보자. A 단말에서 B 단말까지 네트워크 통신을 해야할 때, 수 많은 네트워크 경로가 있을 것이다. 이 중 최소 비용으로 보내는 것이 경제적이기 때문에 실제로 네트워크망을 구축할 때 주요하게 사용된다. 이 외에도 물자 배송, 도시간 도로 연결, 이미지 프로세싱 등 다양한 곳에서 사용되고 있다.
따라서 MST를 구하는 과정이 어려울 것 같지만, 지금까지 위에서 설명했던 알고리즘에 약간의 조건만 더 추가하면 알고리즘을 구현할 수 있다.
크루스칼 알고리즘 (Kruskal Algorithm)
크루스칼 알고리즘은 MST를 구하는 대표적인 알고리즘 중 하나로 그리디 알고리즘으로 분류된다. 과정은 다음과 같다.
- 간선 데이터를 오름차순 정렬한다.
- 간선을 하나씩 순회하며 사이클 발생 여부를 확인한다.
- 사이클이 발생하지 않으면 MST 집합에 포함한다.
- 사이클이 발생하면 패스한다.
- 모든 간선에 대해서 MST 집합에 포함되는 간선의 개수가 (노드의 개수 - 1)개일 때까지 2번의 과정을 반복한다.
본 글에서 지금까지 쭉 설명해 왔던 것들이다. 직접 예시를 들어 보자.
위 그래프의 간선 정보를 입력 받았을 때, 이를 오름차순 정렬한 표가 아래와 같다.
| 간선 | (2, 3) | (3, 5) | (5, 6) | (2, 5) | (1, 2) | (3, 4) | (4, 5) |
| 비용 | 1 | 2 | 3 | 5 | 10 | 11 | 30 |
이제 위 알고리즘대로 간선들을 하나씩 순회해 보자. 물론 이때 각 노드들은 자신을 부모로 하도록 초기화 되어있는 상태여야 한다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 2 | 3 | 4 | 5 | 6 |
[간선 (2, 3)]
- 노드 2와 노드 3의 부모 확인 (
find) - 부모가 다르므로 사이클 발생 X
- 두 노드의 부모를 연결 (
union) - MST 집합에 포함
위 과정을 [간선 (5, 6)]까지 한 결과는 다음과 같다.
| 간선 | (2, 3) | (3, 5) | (5, 6) | (2, 5) | (1, 2) | (3, 4) | (4, 5) |
| 비용 | 1 | 2 | 3 | 5 | 10 | 11 | 30 |
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 |
| 부모 | 1 | 2 | 3 | 4 | 5 | 6 |
총 3개의 간선이 MST에 포함됐고, 4개의 노드를 연결했다. 이제 다음 간선을 확인해 보자.
[간선 (2, 5)]
- 노드 2와 노드 5의 부모 확인 (
find) - 부모가 같으므로 사이클 발생
이 간선은 사이클을 발생시키므로 비용이 적더라도 넘어가면 된다. 이렇게 마지막 간선은 순회할 필요없이 [간선 (3, 4)]까지 순회하면 MST에 포함되는 간선의 개수가 5개로 MST가 완성된다.
| 간선 | (2, 3) | (3, 5) | (5, 6) | (2, 5) | (1, 2) | (3, 4) | (4, 5) |
| 비용 | 1 | 2 | 3 | 5 | 10 | 11 | 30 |
마지막으로 크루스칼 알고리즘의 성능을 분석해 보면, 간선의 개수가 E일 때, O(ElogE)의 시간 복잡도를 가지게 된다. 이는 사실 간선들을 오름차순 정렬하는 데에서 발생하는 비용이다. 보통 정렬을 할 때 각 언어의 표준 라이브러리를 사용하면 O(ElogE) 만큼의 시간 복잡도가 소요된다.
이 외에도 MST를 구하는 방법에는 프림 알고리즘(Prim’s Algorithm)도 있다. 간선을 기준으로 하는 크루스칼 알고리즘과는 달리 정점을 기준으로 하는데, 다익스트라(Dijkstra) 알고리즘과 거의 유사하니 찾아보면 좋을 것 같다.