Union-Find Algorithm

https://m.blog.naver.com/PostView.naver?blogId=ndb796&logNo=221230967614&referrerCode=0&searchKeyword=union 

17. Union-Find(합집합 찾기)

(위 안경잡이개발자 님의 블로그를 보고 공부했습니다.) 

 

 

Union-Find 알고리즘은 이름 그대로 union(합하고), Find(찾는) 알고리즘이다. 

서로소 집합 (Disjoint-set) 알고리즘이라고도 불리는데, 두 노드를 선택했을때 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이기 때문이다. 

 

알고리즘이 작동하는 방식은 다음과 같다.

 

1. 모든 노드들은 최초에 자기 자신을 부모 노드로 갖는다.

 

2. 서로 다른 두 노드를 연결할때 (Union), 하나의 노드의 부모를 또다른 하나의 노드로 수정한다. (부모를 합칠때는 일반적으로 더 작은 값이 부모가 되도록 합친다)

 

3. 어떤 노드의 부모를 찾을때는 (Find) 재귀적으로 부모를 거슬러 올라가며 찾는다. 

 

#include <iostream>
#include <vector>
using namespace std;

// 노드의 부모를 재귀적으로 찾는다 (가장 위의 루트가 몇번 노드인가?)
int getParent(vector<int> &parent, int x)
{
    if(parent[x] == x) return x;
    return parent[x] = getParent(parent, parent[x]);
}

// Union
// 두 노드를 잇는다
void unionParent(vector<int> &parent, int a, int b)
{
    a = getParent(parent, a);
    b = getParent(parent, b);
    // 더 작은 노드를 부모로
    if(a < b) parent[b] = a;
    else parent[a] = b;
}

// Find
// 두 노드 a와 b가 그래프상 이어져있는지 탐색한다
// 이어져있다면 true, 아니라면 false 리턴
bool findParent(vector<int> &parent, int a, int b)
{
    a = getParent(parent, a);
    b = getParent(parent, b);
    if(a == b) return true;
    else return false;
}


int main()
{
    // 최초에 각 노드는 자기 자신이 부모이다
    vector<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);

    // 노드 1과 5가 그래프상 서로 이어져있는가?
    cout << findParent(parent, 1, 5) << endl;
    unionParent(parent, 1, 5);
    cout << findParent(parent, 1, 5) << endl;
}