안녕하세요 기린입니다 :)
이번 시간에 배워볼 내용은 바로 크루스칼 알고리즘입니다. 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 다시 말해 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이라고 할 수 있습니다. 예를들어 여러 개의 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자 할 때 실제로 적용되는 알고리즘이죠
일단 용부터 정리해보겠습니다
- 노드 = 정점 = 도시 -> 그래프에서 동그라미에 해당하는 부분
- 간선 = 거리 = 비용 -> 그래프에서 선에 해당하는 부분
즉 아래의 그래프를 살펴보았을 때 노드의 갯수는 7개, 간선의 갯수는 11개 입니다.
크루스칼의 핵심 개념은 간선의 거리가 짧은 순서대로 그래프에 포함시키자 입니다. 일단 모든 노드를 최대한 적은 비용으로 '연결만' 시키면 되기 때문에 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근차근 그래프에 포함시키면 되는 것입니다.
일단 위와 같이 모든 간선들의 정보를 저장합시다. 노드 1부터 노드 7까지 연결된 모든 간선 정보를 저장한 것입니다. 보시면 노드 6, 7은 간선 정보가 없는데 그 이유는 이미 다른 노드들의 간선 정보에 모두 포함이 되어있기 때문입니다. 이렇게 살펴보니 간선이 총 11개가 존재합니다.
위와 같이 모든 간선들을 거리(비용)를 기준으로 오름차순 정렬을 수행했습니다. 이제부터 다음 순서에 맞게 그래프를 연결하시면 가장 적은 비용으로 모든 노드를 연결한 그래프인 '최소 비용 신장 트리'가 만들어집니다.
1. 정렬된 순서에 맞게 그래프에 포함시킵니다.
2. 포함시키기전에는 사이클 테이블을 확인합니다.
3. 사이클을 형성하는 경우 간선을 포함하지 않습니다.
여기에서 사이클이라는 것은 말 그대로 그래프가 서로 연결되어 사이클을 형성하는 경우입니다. 최소 비용 신장 트리에서는 사이클이 발생하면 안 됩니다. 애초에 모든 노드를 이어붙이기만 하면 되는데 사이클이 발생할 이유가 없겠죠 :]
사이클이 발생하는지의 여부는 지난 시간에 배운 Union-Find 알고리즘을 그대로 적용하시면 됩니다. 바로 한번 시작해보도록 하겠습니다. 아래 그림은 초기 상태입니다.
이제 바로 첫 번째 간선부터 선택해보겠습니다.
두 번째 간선을 선택하겠습니다.
세 번째 간선을 선택해봅시다.
자 이런식으로 쭉 가다 1과 4 즉 비용이 28인 경우를 보시겠습니다.
이 때 1과 4가 이미 연결이 되어있으므로 무시하고 넘어가게 되는거죠. 자 이렇게 마지막까지 진행해보면
사이클 테이블의 모든 값이 1이 되면서 최소 비용 신장 트리가 만들어진 것을 알 수 있습니다. 나머지 남은 간선 4개는 모두 스팁(Skip) 처리되면서 결과적으로 다음과 같이 완성됩니다.
총 비용 -> 12 +13 + 17 +20 +24 + 37 = 123
따라서 전체 노드를 연결하는 최소 비용은 123입니다.
원리를 이해하셨나요? 그럼 소스코드로 구현해봅시다. :)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 부모 노드를 가져옴
int getParent(int set[], int x) {
if(set[x] == x) return x;
return set[x] = getParent(set, set[x]);
}
// 부모 노드를 병합
void unionParent(int set[], int a, int b) {
a = getParent(set, a);
b = getParent(set, b);
// 더 숫자가 작은 부모로 병합
if(a < b) set[b] = a;
else set[a] = b;
}
// 같은 부모를 가지는지 확인
int find(int set[], int a, int b) {
a = getParent(set, a);
b = getParent(set, b);
if(a == b) return 1;
else return 0;
}
// 간선 클래스 선언
class Edge {
public:
int node[2];
int distance;
Edge(int a, int b, int distance) {
this->node[0] = a;
this->node[1] = b;
this->distance = distance;
}
bool operator <(Edge &edge) {
return this->distance < edge.distance;
}
};
int main(void) {
int n = 7;
int m = 11;
vector<Edge> v;
v.push_back(Edge(1, 7, 12));
v.push_back(Edge(1, 4, 28));
v.push_back(Edge(1, 2, 67));
v.push_back(Edge(1, 5, 17));
v.push_back(Edge(2, 4, 24));
v.push_back(Edge(2, 5, 62));
v.push_back(Edge(3, 5, 20));
v.push_back(Edge(3, 6, 37));
v.push_back(Edge(4, 7, 13));
v.push_back(Edge(5, 6, 45));
v.push_back(Edge(5, 7, 73));
// 간선의 비용으로 오름차순 정렬
sort(v.begin(), v.end());
// 각 정점이 포함된 그래프가 어디인지 저장
int set[n];
for(int i = 0; i < n; i++) {
set[i] = i;
}
// 거리의 합을 0으로 초기화
int sum = 0;
for(int i = 0; i < v.size(); i++) {
// 동일한 부모를 가르키지 않는 경우, 즉 사이클이 발생하지 않을 때만 선택
if(!find(set, v[i].node[0] - 1, v[i].node[1] - 1)) {
sum += v[i].distance;
unionParent(set, v[i].node[0] - 1, v[i].node[1] - 1);
}
}
printf("%d\n", sum);
}
크루스칼 알고리즘은 사실상 정렬 알고리즘과 Union-Find 알고리즘의 합이라고 할 수 있으므로 정렬 알고리즘의 시간 복잡도와 동일하다고 판단해도 큰 무리가 없습니다.
자 그럼 즐거운 코딩하세요 :)
문의: ralla0405@gmail.com
