[자료구조] Union-Find, 유니온파인드

 + 이 글은 작성자가 직접 공부하고 복습하며 작성한 글입니다. 만약 직접 작성하지 않았다면, 꼭 출처를 밝히겠습니다!

 + 이 글은 개인적인 공부를 바탕으로 작성되었기에, 틀린 부분이 있을 수 있으며, 틀린 부분이 있다면 알려주시면 감사하겠습니다!

 + 이 글을 다른 곳으로 가져가신다면, 꼭 출처를 남겨주세요~

 + '참고사이트'는 공부하기 위해 참고한 사이트들을 모아 둔 것입니다.

 + 혹시라도 문제가 된다면 바로 조취를 취할테니, 말해주시면 감사하겠습니다!

<Union-Find>

[What?]

 + Union-Find는 Disjoint set(서로소 집합) 또는 Merge Find Set(병합 찾기 집합)이라고도 불리는 서로 연관되어있는 것끼리만 묶여있는 자료구조를 뜻합니다.

 + 무분별한 노드(하나의 개체)들이 있을 때, 각 노드들은 자신의 집합의 root정보를 가지고 있고, 그 정보를 비교해서 원하는 결과를 얻으려고 할 때, 사용하는 자료구조입니다.

 + 모든 노드들은 자신의 root정보로 집합이 엮여있으므로, 트리구조(2진트리X)를 따릅니다.

 + 예를 들자면,

1)  A,B,C,D,E 와같이 5개의 노드가 있다고했을 때, 각 노드는 자신을 하나의 집합이라고 생각하고, 그 집합의 루트 정보를 가지고 있습니다. 그 루트 정보를 가지고 같은 집합인지 비교하는 것입니다.

=> A(A), B(B), C(C), D(D), E(E)

2) 여기서, A와 B를 비교해서 root가 다르면 같은 집합으로 묶어주고, C와 D를 비교해서 root가 다르면 같은 집합으로 묶어줍니다.

=> {A(A), B(A)}, {C(C), D(C)}, E(E)-여기서 누가 root가 될 건지는 개발자 마음입니다.

3) 여기서 E와 A의 루트와 비교해서 root가 다르다면 같은 집합으로 묶어 줍니다.

=> {A(A), B(A), E(A)}, {C(C), D(C)}

 + 위와 같은 방법으로 자료구조를 형성하여 사용하는 것이 Union-Find입니다.

[Use]

 + 일반적인 구조는 아래와 같은 형태를 가집니다.

void findFunc(int x) {

    if (parent[x] == x) return x;

    return find(parent[x]);    // 자신의 root를 찾아서 반환합니다.

 

void uniFunc(int x, int y) {

    parent[y] = x;    // 자신의 root를 x로 바꿔, 해당 집합으로 들어갑니다.

}

 + 이렇게 하면 1열로 늘어진 자료구조가 나올 수 있습니다.(시간복잡도 n)왜냐하면, uni할 때 마다 부모인 노드가 다른 노드의 자식으로 들어가버리니까요.

 + 그걸 방지하고자, 각 집합의 부모를 찾아서, 그 부모의 자식이 되도록 설정합니다.

void uniFunc(int x, int y) {

    x = find(x);

    y = finx(y);

    if (x == y) return;

    parent[y] = x;

}

 + 이 방법에서 더 진보된 방법이있습니다. 그건, 각 집합의 높이를 비교해서 낮은 쪽을 높은 쪽으로 합치는 것입니다. 그렇게 되면, 합친 트리의 높이가 증가하지 않습니다. 시간복잡도가 더 늘어나지 않기 때문에, 위의 방법보다 더 빠른 찾기가 가능합니다.

void uniFunc(int x, int y) {

    x = find(x);

    y = find(y);

    if (x == y) return;

    if (rank[x] < rank[y]) parent[x] = y;

    else parent[y] = x;

    if (rank[x] == rank[y]) rank[x]++;

}

 + 여기서 rank는 높이를 뜻하고, 마지막의 rank비교문에서 x를 증가시켜주는 것은, 높이가 같을 때, x의 자식으로 y가 들어가도록 설정해두었기 때문입니다. 그렇기에 자신의 상황에 따라서 수정하면 됩니다.

 + 유니온 파인드에서 부모를 한 번 설정하면 끝까지 부모로 설정됩니다. 그렇기 때문에, 한 번 find()해서 루트 부모를 찾으면, 평생 루트 부모로 존재할 것이고, 내 부모가 될 수 있습니다. 그렇기에, 한 번 찾을 때, 최종 루트 부모를 찾아서 설정해둔다면 빠른 찾기가 가능할 것입니다.(참고로 최고 루트는 자기자신이 부모로 설정되어있다.)

void uniFunc(int x, int y) {

    x = find(x);

    y = finx(y);

    if (x == y) return;

    if (rank[x] < rank[y]) parent[x] = y;

    else parent[y] = x;

    if (rank[x] == rank[y]) rank[x]++;

}

 

int findFunc(int x) {

    return parent[x] == x ? x : parent[x] = find(parent[x]);

}

[Comment]

 + 대부분의 경우도 마찬가지지만, Union-Find는 자료구조이기에, 어떤 식으로 구성되어있는지만 익혀두고, 사용은 개발자분들 알아서, 상황에 맞게 변경해서 사용하셔야 합니다!!!

[문제추천]

https://www.acmicpc.net/problem/2463

http://koistudy.net/?mid=prob_page&NO=962

---

** 참고사이트 **

 - https://twpower.github.io/115-union-find-disjoint-set

 - http://weeklyps.com/entry/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Unionfind

 - 

 - 

Copyright © -강정이좋아- 무단 전재 및 재배포는 하지 말아주세요.