유니온 파인드(Union Find, Disjoint Set)

유니온 파인드(Union Find)란?

유니온 파인드(Union Find)는 Disjoint Set라고도 불리기도 하며, 이 자료구조는 일상속에서 우리가 은연중에 접하는 자료구조이다.

예를 들어보자. 

우리는 학창 시절에 수학여행을 가서 동요를 틀어두고 있다가 갑자기 조교가 3명!이라고 하면 3명끼리 뭉쳐본 적이 있을 것이다.

그리고 그 3명은 계속 같이 다니게 되고 또 거기서 6명을 외치면 3명과 다른 영역에 있던 3명이 합쳐 6명이 되는 

그런 게임을 해본적이 있다.(유니온 파인드 설명을 위해 적다보니 원래 게임 룰과 조금 달라진 것 같기도 하다.) 

이 게임을 이제 유니온 파인드에 접목해보자.

처음에 3명이 뭉치기 전 각각 1명씩은 독립적인 트리이다.(노드가 1개이고 루트가 자기 자신인 트리)

이 후 3명이 뭉치게 되면 3개의 노드는 하나의 트리를 이루게 된다.(그중 하나가 루트가 된다.)

또 6명이 뭉치게 되면 3개의 노드를 가진 트리 두개가 6개의 노드를 가지는 트리로 합쳐진다.

이러한 자료구조를 이번 게시물을 통해 알아보고자 한다.

유니온 파인드(Union Find)에 이용할 함수

1. 초기화 과정(init)

    // 초기에는 자신의 부모는 자기 자신
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
        level[i] = 1;
    }

함수는 아니지만, 초기화 과정이다. (함수로 만들면 함수가 된다.)

parent[i] = i :: 현재 자신의 부모는 루트 노드인 자기 자신으로 초기화한다.

level[i] = 1 :: 초기에 트리의 level은 1로 초기화한다.

2. 파인드 과정(find)

유니온 과정 속에 파인드 함수가 들어가있기에 파인드 과정을 먼저 설명 한다.

int find(int u)
{
    // 루트 노드이면 return u
    if (u == parent[u])
        return u;
 
    // 그 외에는 자신의 루트를 찾으러 간다.
    return parent[u] = find(parent[u]);
}

u == parent[u]의 의미는 결국 u의 루트 노드가 자기 자신이냐를 묻는 것이다.

자기 자신이 루트 노드라면 return u를 하여 find 함수를 탈출하고,

자기 자신이 루트 노드가 아니라면 자신의 트리에서 루트 노드를 찾으러 간다.

이때 유니온 파인드를 위해 형성된 트리는 무조건 find함수를 종료할 수 있다.

그 이유는 결국 최상위 루트 노드는 자기 자신을 루트 노드로 가리키고 있기 때문이다.

이렇게 루트 노드를 찾아 return u를 하게 되면 parent[u]도 return값으로 u를 받으며 

모든 노드의 루트 노드를 최상위 노드로 변경시켜 줄 수 있다.

아래 그림을 보면서 find가 어떻게 동작하는지 알아보자

우선 아래와 같이 u가 있고 find(u)를 실행해보자.

u != parent[u]이기에 return parent[u] = find(parent[u])를 호출하게 되고 u의 부모인 한칸 위의 노드로 향하게 된다.

u의 부모 노드도 u != parent[u]이기에 또 한칸 더 위로 올라가게 된다.

가장 위(루트)노드는 u == parent[u]를 만족하게된다. 따라서 return u;를 하게 됐고

루트 바로 아래 노드는 parent[u] = root를 받고 return parent[u]를 하게 된다.(즉 루트 노드가 무엇인지 return 해준다.)

최종적으로 u 또한 parent[u] = root를 받게 되고 최종적으로 find함수가 끝나게 된다.

하지만 이 그림에서 모든 find 함수가 종료되었다고 생각하면 안된다.

u의 부모가 현재 루트 노드로 변했다.(parent[u] = root에 의해)

따라서 변형된 트리를 관찰해 볼 필요가 있다.

이 트리가 최종적으로 find(u)를 실행하고 난 뒤의 결과물로 나타나는 트리이다.

유니온 파인드를 단순하게 나타낼 수도 있지만, 유니온 파인드 자료구조 또한 tree형이기에 우측 혹은 좌측으로 치우쳐진 트리가 생긴다면 매우 오랜 시간이 걸릴 수 있다.

따라서 이 과정을 경로 압축 최적화라 하고 경로 압축을 하지 않은 자료구조는 이 게시물에서 따로 보여주지 않는다.

(사실 return parent[u] = find(parent[u])에서 return find(parent[u])로 쓴다면 압축되지 않은 유니온 파인드가 된다.)

3. 유니온 과정(union)

아쉽게도 union이라는 것은 예약어이기 때문에 union이라는 함수명을 쓸 수 없다. 

따라서 보편적으로 merge라는 이름으로 유니온을 표현한다.

void merge(int u, int v)
{
    u = find(u);
    v = find(v);
 
    // 루트가 같다면 이미 같은 트리
    if (u == v)
        return;
 
    // u가 v보다 더 깊은 트리라면 swap
    if (level[u] > level[v])
        swap(u, v); // 항상 u가 더 작은 트리가 되도록 한다. 
 
    // u의 루트가 v가 되도록
    parent[u] = v;
 
    // u와 v의 깊이가 같을 때 v의 깊이를 늘려준다.
    if (level[u] == level[v])
        ++level[v];
}

u의 노드가 있는 트리와 v의 노드가 있는 트리를 합칠 예정이다.

아래와 같이 u와 v노드를 서로 가진 트리를 보자.

union의 첫 과정인 u = find(u), v = find(v)를 통해 u와 v의 루트 노드를 알아낸다.

결과적으로 u = r1이 되고 v = r2가 될 것이다.

u == v 즉, r1 == r2이면 return;하여 union을 중단하게 되지만, 현재 그런 상황이 아니므로 다음 코드 라인을 본다.

if(level[u] > level[v]) swap(u,v);를 통해 위의 트리는 다음과 같이 바뀌게 된다. 이때 u = r1, v = r2임을 알고있어야 한다.

이후 parent[u] = v(즉, parent[r1] = r2)를 통해 두 트리를 하나의 트리로 합쳐준다.

만약 두 트리가 같은 레벨의 트리였다면 루트 노드가 되는 level 배열을 1 늘려주면 된다.

이 과정이 if(rank[u] == rank[v]) ++ rank[v]; 이다.

시간 복잡도

유니온 파인드(Union Find) 자료구조는 매우 간단하면서 매우 좋은 효율을 자랑한다.

시간 복잡도 측면을 생각해보자.

일단 경로 압축을 통해 우리는 트리를 압축시켰다.

따라서 find의 시간 복잡도는 다음과 같게 변한다.

find :: O(lgN)

그다음 union의 시간 복잡도를 보자.

union도 자세히 보면 find에 지배 받음을 알 수 있다.

결국 union의 시간 복잡도도 다음과 같아진다.

union :: O(lgN)

사실 아주 정확하게 말하자면 find 연산은 호출할 때마다 수행 시간이 변한다. 따라서 매우 까다로운 시간 복잡도를 가지고 있는데

실제 시간 복잡도는 O(α(N))이라고 한다. α는 애커만 함수라고 하는데 N이  2^65536일때 애커만 함수 값이 5가 된다.

따라서 그냥 상수라고 봐도 무방하다.

이 자료구조는 매우 쉬워 보이나, 문제에 대한 힌트 없이 주어진 문제를 파악할 때 

이 문제가 유니온 파인드 문제인지 알 수 있는 능력이 매우 중요하다.

이 자료구조에 대한 가장 기초적인 문제 2가지를 풀어본다면 유니온 파인드에 대해 많은 감각이 생길 것이다.

[1717번] 집합의 표현 :: http://www.crocus.co.kr/684

[1976번] 여행 가자 :: http://www.crocus.co.kr/685