Union-Find

🧩 Union-Find란?

Union-Find는 A와 B가 이미 같은 그룹인지 확인하고 아니면 같은 그룹으로 합치는 기능이다.

 

Kruskal 알고리즘에서는 Union-Find를 이용해 새로운 간선을 선택했을 때 사이클이 생기는 판별한다.

find(x)

x가 속한 그룹의 대표를 찾는다. 예를 들어 {1, 2, 3}이라는 그룹의 대표가 1이라면

find(1) = 1
find(2) = 1
find(3) = 1

이 된다.

union(a, b)

a가 속한 그룹과 b가 속한 그룹을 하나로 합친다. 예를 들어 그룹 1 = {1, 2}이고 그룹 2 = {3}일 때 union(2, 3)을 실행하면 {1, 2, 3}이 된다.

root 배열

각 그룹이 트리 구조라고 가정해 보자. 여기서 root는 각 노드가 속한 그룹이 어떤 노드를 트리의 루트로 가리키는지 저장한다. 물론 이름은 사람마다 다르게 작성할 수 있으며 parent라고 쓰는 경우도 있다.

int[] root = new int[V+1];

처음에는 모두 자기 자신이 그룹의 대표(깊이가 1인 트리의 노드)다.

for (int i = 1; i <= V; i++) {
	root[i] = i;
}

[그림 1]

🧩 Find

기본적인 find 함수는 다음과 같다.

static int find(int x) {
    if (parent[x] == x) {
        return x;
    }

    return find(parent[x]);
}

 

만약 root[3] = 2이고 root[2] = 1이라면 다음과 같이 될 것이다.

[그림 2]

• find(1): parent[1] == 1이므로 자기 자신인 1을 반환한다.
• find(3): find(2) → find(1)을 재귀 호출해 3이 속한 트리의 루트인 1을 반환한다.

경로 압축 (Path Compression)

실제로는 다음과 같은 형태로 사용한다.

static int find(int x) {
    if (root[x] == x) {
        return x;
    }

    return root[x] = find(root[x]);
}

 

return parent[x] = find(parent[x]);는 루트를 찾으면서 현재 노드가 루트를 직접 가리키도록 바꾸는 작업을 한 번에 한다.

[그림 3]

[그림 2]에서 find(3)을 하려면 3 → 2 → 1 을 거쳐야 하지만, [그림 3]에서 find(3)을 하면 바로 1을 찾을 수 있어서 코드 실행 속도가 더 빨라진다.

🧩 Union

static boolean union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);

    // 이미 같은 그룹
    if (rootA == rootB) {
        return false;
    }

    // 두 그룹 합치기
    root[rootB] = rootA;

    return true;
}

• A와 B가 이미 같은 그룹이면 false 반환
• A와 B가 서로 다른 그룹이면 두 그룹을 합치고 true 반환

[그림 4]

[그림 4]에서 union(2, 5)를 호출하면 rootA가 1, rootB가 4가 되어 실제로는 그룹의 루트끼리 연결하게 된다.

[그룹 5] 두 그룹을 합친 후

두 그룹을 합친 후 1, 2, 3, 4, 5는 모두 같은 그룹이 되었다.

rank 배열

더 효율적인 Union-Find 알고리즘을 구현하기 위해 rank 배열을 사용하기도 한다.

static int[] root;
static int[] rank;

 

rank는 트리의 높이 정보를 저장한다. 트리가 한쪽으로 너무 길어지면 find()가 느려질 수 있기 때문에, 작은 그룹을 큰 그룹 아래에 붙이는 방식이다.

static boolean union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);

    if (rootA == rootB) {
        return false;
    }

    // A 트리가 더 낮으면 A를 B 밑으로
    if (rank[rootA] < rank[rootB]) {
        root[rootA] = rootB;
    }

    // B 트리가 더 낮으면 B를 A 밑으로
    else if (rank[rootA] > rank[rootB]) {
        root[rootB] = rootA;
    }

    // 높이가 같으면 아무 쪽이나 부모가 될 수 있음
    else {
        root[rootB] = rootA;

        // 같은 높이끼리 합쳤으므로 높이가 커질 수 있음
        rank[rootA]++;
    }

    return true;
}

• A 트리가 더 낮은 경우 (rank[A] < rank[B]) : A를 B 밑으로 붙임 ― 큰 트리 밑에 작은 트리를 붙이면 전체 높이가 거의 늘어나지 않기 때문
• B 트리가 더 낮은 경우 (rank[A] > rank[B]) : B를 A 밑으로 붙임
• 둘의 높이가 같은 경우 (rank[A] == rank[B]) : 둘 중 아무 쪽이나 부모로 해도 되지만, 높이가 같은 트리를 합치면 전체 트리 높이가 1 증가할 수 있으므로 부모가 된 쪽의 rank를 1 증가시킴