[알고리즘] Union Find

서론

올해 초부터 어느정도 적당한 난이도 이상의 코딩테스트들에 응시하고 있는데,

항상 5번문제는 MST관련 문제가 나왔다. 조금만 변형되어도 풀기가 애매해질 정도로 얕은 정도로만 학습을 한 상태였기 때문에, 복기를 위해 관련된 것들을 학습하려고 한다.

 

 

 

Union Find

Disjoint Set(서로소 집합)을 관리하는 데 사용되는 알고리즘으로, 각 집합의 대표 요소를 통해 집합을 식별한다. 대표 요소를 해당 집합의 부모라고도 부르며, 루트로 표현된다. 일반적으로 작은 번호를 부모로 정하는데, 이는 트리의 높이를 최소화하여 연산의 효율성을 높일 수 있다.

 

여러 노드가 존재할 때, union과 find 연산을 수행한다.

Union : 노드를 연결

Find : 특정 노드의 루트 노드를 찾음

 

 

 

예제

 

원소	A	B	C
부모	A	A	C

1. A,B,C 세 요소가 존재할 때, A와 B를 연결한다. 연결 시 B의 부모는 A가 된다.

 

원소	A	B	C
부모	A	A	B

2. B와 C를 연결했을 때, C의 부모요소는 B이다. 이 때, B의 부모요소는 A이며, 그렇다면 C의 부모요소는 결국 A가 될 것이다. 그렇다면 아래와 같이 그림이 변하게 된다.

 

 

원소	A	B	C
부모	A	A	A

3. 결국 B와 C 모두 부모는 A이다.

 

이 예시에서 C의 부모를 찾는 과정에서, C의 부모는 B였고, C의 부모를 B로 나타냈다. 하지만 B의 부모는 A였기 때문에 연산을 종료하지 않고 다시 A까지 가는 과정을 거쳤다.

 

이처럼, Union Find에서 부모 요소를 찾을 때, 재귀적으로 루트 노드를 찾을 때 까지 계속해서 반복한다.

 

 

private static void union(int a, int b) {
    a = find(a);
    b = find(b);
    if(a != b)
        parent[b] = a;
}

union할 때, 당연한 말이지만 서로 연결이 되지 않은 상태였기 때문에 연결을 수행했다. 연결이 되지 않은 상태를, 서로의 부모가 누군지를 통해 파악하며, 부모가 다르다면 한 요소를 다른 요소의 부모로 변경하여, 연결됨을 표현했다.

 

private static int find(int a) {
    if(parent[a] == a)
        return a;
    else
        return parent[a] = find(parent[a]);
}

또한 union할 때, find를 통해 두 요소가 각각 어떤 집합에 속해있으며, 그 집합의 루트 노드는 누구인지를 찾아서 union을 수행한다. 그렇기 때문에 재귀적으로 해당 요소의 뿌리를 찾아가는 것이다.