[알고리즘 공부] 합집합 찾기(Union-Find), 크루스칼 알고리즘

유니온 파인드(Union-Find, 합집합 찾기)

대표적인 그래프 알고리즘. 서로소 집합(Disjoint-Set) 알고리즘이라고도 부름.

여러개의 노드가 존재할 때 2개의 노드를 선택해, 현재 이 노드들이 서로 같은 그래프에 속하는지 판별.

나중에 strongly connected component, 크루스칼(Kruskal) 알고리즘 등과 같은 고급 알고리즘에서도 적용되는 원리로
활용도가 높으므로 잘 공부하고 넘어가는 것이 좋음.

 

- 합침(Union) : 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합침

- Find 알고리즘 : 2개 노드의 부모 노드를 확인해 현재 같은 집합에 속하는지 확인하는 알고리즘

 

자식	1	2	3	4	5	6
부모	1	2	3	4	5	6

• 맨 처음에는 집합 자체가 각각 다 자기 자신을 부모로 가지고 있음 => 모든 원소가 자기 자신을 가지고 있음.

 

자식	1	2	3	4	5	6
부모	1	1	3	4	5	6

• 1과 2가 연결되면 더 작은 값을 부모로 가지게 함.

 

자식	1	2	3	4	5	6
부모	1	1	2	4	5	6

• 2와 3이 연결되면 더 작은 값을 부모로
• 1과 3이 연결되었는지는 어떻게 파악할 수 있는지. 부모 노드만 보고는 한번에 파악 불가능
  => 재귀 함수가 사용됨.

 

자식	1	2	3	4	5	6
부모	1	1	1	4	5	6

• 3의 부모 찾기: 3이 가리키고 있는 2를 찾고, 2의 부모가 1을 가리키고 있으므로 ‘결과적으로 3의 부모는 1이 됨’
• 노드 1,2,3의 부모가 모두 1이므로 이 세 노드는 모두 같은 그래프에 속함.

 

#include <stdio.h>

// 부모 노드를 찾는 함수
int getParent(int parent[], int x) {
    // x 값이 해당 부모의 값과 동일하면 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;
}

int main() {
    int parent[11];
    // 자기자신을 부모로 가리키도록 만듦 (각각 개별적인 원소로 떨어져있음)
    for (int i = 1; i <= 10; i++) {
        parent[i] = i;
    }
    unionParent(parent, 1, 2);
    unionParent(parent, 2, 3);
    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)

간선을 거리가 짧은 순서대로 그래프에 포함

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘. 즉, 최소비용 신장 트리를 만들기 위한 대표적인 알고리즘

<용어>

• 노드 = 정점 = 도시: 그래프에서 동그라미에 해당
• 간선 = 거리 = 비용: 그래프에서 선에 해당

모든 노드를 연결하기 위한 최소 간선 개수 = 노드 개수 - 1

 

우선 간선 정보를 오름차순으로 정렬한 뒤, 비용이 적은 간선부터 그래프에 포함
주의할 점: 최소 비용 신장 트리에서는 사이클이 발생하면 안됨.

그러므로,

1. 정렬된 순서에 맞게 그래프에 포함
2. 포함시키기 전 사이클 테이블을 확인
3. 사이클을 형성하는 경우 간선 포함 X

 

- 사이클 발생 여부는 Union-Find 알고리즘을 그대로 적용. 부모가 같은 경우 사이클 형성하는 것이므로 무시하고 넘김

- 사이클 테이블 초기에는 자기 자신을 가리키도록 함 - 부모 테이블과 동일

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 부모 노드를 찾는 함수
int getParent(int set[], int x) {
    // x 값이 해당 부모의 값과 동일하면 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 findParent(int set[], int a, int b) {
    a = getParent(set, a);
    b = getParent(set, 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() {
    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;
    }

    int sum = 0;
    for (int i=0; i< v.size(); i++) {
        // 동일한 부모를 가리키지 않는 경우, 즉 사이클이 발생하지 않을 때만 선택
        // -1을 해주는 이유: set의 인덱스와 값의 범위가 0~6이므로 각 노드에서 1씩 빼줘야 함.
        if(!findParent(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);

    return 0;
}

 

크루스칼 알고리즘은 사실상 정렬 알고리즘과 Union-Find 알고리즘의 합이라고 할 수 있으므로,
정렬 알고리즘의 시간 복잡도와 동일하다고 판단해도 큰 무리가 없음.

크루스칼 알고리즘은 주기적으로 대회에 출제된다고 하니 잘 공부해둘 것.