합집합 찾기(Union-Find), 크루스칼 알고리즘(Kruskal Algorithm)

합집합 찾기 (Union-Find)

합집합 찾기는 대표적인 그래프 알고리즘으로, 서로소 집합 알고리즘이라고도 부른다. 여러 개의 노드가 존재할 때 두개의 노드를 선택해서 두 개의 노드가 서로 같은 그래프에 속하는지(합집합인지) 판별하는 알고리즘이다.

그럼 찬찬히 합집합 찾기 알고리즘에 대해 알아보자.

 

먼저 노드의 수 만큼의 배열의 모든 값이(모든 노드가) 자기 자신을 가리키도록 초기화를 한다. 그 후 노드 두개가 연결된다면, 두개의 노드 중 작은 값으로 값을 업데이트한다. 예를 들어 1과 2가 연결되면 원래 2였던 parent[2] 값이 1이 되는 것이다. 이것이 바로 합침(Union)이다.

그런데 이때 2와 3이 연결된다면 parent[3]=2가 된다. 이렇게 되면 1과 3이 연결되었는지를 한번에 파악할 수 없기 때문에 재귀를 사용해 parent[3]이 1이 되도록한다. 즉, 먼저 3이 가리키는 2를 찾고 2가 가리키는 1을 찾아 결과적으로 3의 부모는 1이 되는 것이다.

 

그럼 추가로 이해를 돕기 위한 그림을 살펴보자.

Union-Find 알고리즘의 코드는 아래와 같다.

 

#include <stdio.h>
 
//부모 노드 찾는 함수
int getParent(int parent[], int x) { //부모(연결된 것들/합집합 중 가장 작은수) 찾기
    if (parent[x] == x)
        return x;
    return parent[x] = getParent(parent, parent[x]); //재귀 사용
}
 
// 두 부모 노드를 합치는 함수(연결하는 함수)
int unionParent(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}
 
// 같은 부모를 가지는지 확인
int findParent(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a == b) return 1;
    return 0;
}
 
int main() {
    int parent[11] = { 0, };
    for (int i = 1;i <= 10;i++) {
        parent[i] = i;
    }
 
    unionParent(parent, 1, 2);
    unionParent(parent, 3, 2);
    unionParent(parent, 3, 4);
    unionParent(parent, 5, 6);
    unionParent(parent, 6, 7);
    unionParent(parent, 7, 8);
 
    printf("1과 5는 연결되어 있나요? %d\n", findParent(parent, 1, 5));
    unionParent(parent, 1, 5);
    printf("1과 5는 연결되어 있나요? %d\n", findParent(parent, 1, 5));
    return 0;
}

 

추가로, 합집합 찾기 알고리즘은 크루스칼 알고리즘에서 사이클 여부를 검사하는데 사용이 된다.

그럼 지금부터 크루스칼 알고리즘에 대해 알아보자.

 

크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘은 가장 적은 비용으로 노드를 연결하기 위해 사용되는 알고리즘, 즉, 최소 비용 신장 트리를 만드는 알고리즘이다.

 

예를 들어, 아래 그림과 같이 노드가 7개, 간선이 11개인 그래프가 있다. 이 그래프를 크루스칼 알고리즘을 사용해 최소 비용 신장 트리(MST)를 알아내 보자.

 

먼저 연결된 노드와 간선의 비용을 가지고 있는 정보를 간선의 크기에 따라 오름차순으로 정렬한다.

그 후 정렬된 순서를 따라 그래프에 포함을 시키는데, 이때, 포함할 간선이 사이클을 형성하는지 검사한 후 사이클을 형성하는 경우에는 간선을 포함시키지 않는다.

이해를 돕기 위해 그림으로 나타내면 다음과 같다.

아래는 크루스칼 알고리즘의 코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
//부모 노드 찾는 함수
int getParent(int parent[], int x) { //부모(연결된 것들/합집합 중 가장 작은수) 찾기
    if (parent[x] == x)
        return x;
    return parent[x] = getParent(parent, parent[x]); //재귀 사용
}
 
// 두 부모 노드를 합치는 함수(연결하는 함수)
void unionParent(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}
 
// 같은 부모를 가지는지 확인
int findParent(int parent[], int a, int b) {
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a == b) return 1;
    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() {
    const 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(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));
    v.push_back(Edge(1, 5, 17));
 
    // 간선의 비용을 기준으로 오름차순 정렬
    sort(v.begin(), v.end());
 
    // 각 정점이 포함된 그래프가 어디인지 저장
    int parent[n];
    for (int i = 0;i < n;i++) {
        parent[i] = i;
    }
 
    int sum = 0;
    for (int i = 0; i < v.size(); i++) {
        // 사이클이 발생하지 않는 경우 그래프에 포함(이미 같은 부모를 가지면 사이클)
        if (!findParent(parent, v[i].node[0] - 1, v[i].node[1] - 1)) {
            sum += v[i].distance;
            unionParent(parent, v[i].node[0] - 1, v[i].node[1] - 1);
        }
    }
    
    printf("%d\n", sum);
    return 0;
}