[나만 몰랐던 알고리즘] Union-Find

Union-Find 는 알고리즘이라고 하기에는 다른 알고리즘에서 많이 쓰이는 부품같은 존재다.

원소 N개가 있을때, 이 원소들을 합집합하는 연산(union)과 특정 원소가 어디 속했는지 구하는 연산(find) 이 두개로 이루어져서 이름도 Union-find 이다.

 

초기화

원소가 N개 있다고 했을때, size = N인 int array parents를 만든다. 이 배열은 해당 인덱스 원소의 부모를 내용으로 가진다.

초기에는 각 원소가 각각의 집합에 속해있다고 가정하므로, parents[i] = i 로 초기화 한다.

int parent[10];

for (int i = 0;i<10;i++){
    parent[i] = i;
}

원소가 속한 곳  찾기

parent[] 배열은 해당 인덱스의 부모를 내용으로 가진다고 했다.

따라서 만약 i 번째 원소가 속한 곳을 찾기 위해선, parent[i]가 가르키는 곳의 부모를 찾아야 한다.

그렇다면 그렇게 찾아 올라가서 더이상 부모가 없는, 가장 우두머리인 경우는 어느 경우일까?

parent[] 원소의 내용이 바뀌지 않았다면, 그 원소는 가르킴 당하기만 하고 다른곳을 가르키지 않는, 우두머리 원소이다.

이 경우, 초기화된 내용 그대론지 확인하여 만약 맞다면 해당 인덱스를 리턴해준다.

그렇지 않은경우 parent[] 원소가 가르키는 곳의 원소를 받아 리턴한다.

int findParent(int a, int parent[]) {
    if (parent[a] == a)
        return a;
    return findParent(parent[a], parent);
}

원소를 합집합 하기

원소의 합집합은 간단하다. 두 원소를 받고, 한 원소의 부모를 다른 원소의 부모로 대입하면 된다.

void unionElement(int a, int b, int parent[]) {
    int pa = findParent(a, parent);
    int pb = findParent(b, parent);

    parent[pa] = pb;
}

---

Union-Find는 다른 복잡한 것(LCA... 같은...) 과 비교하자면 간단하다. 이해하기도 직관적이라 편하다.

대체적으로 이 알고리즘 단독으로 사용되기 보다는 다른 알고리즘과 결합하여 사용되던가, 다른 알고리즘의 구성 요소가 되는 경향이 있는것 같다.

바로 예를 들 수 있는게 MST를 구하는 크루스칼 알고리즘에서 두 노드가 연결되어있는지 확인할때 바로 이 Union-Find를 사용하게 된다.

 

오늘도 평온한 하루가 되길. 슨민.