유니온 파인드 (Union-Find)

유니온 파인드

유니온 파인드는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된다.

union

- 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a, b가 a ∈ A, b ∈ B 일 때 union(a, b)는 A ∪ B를 말한다.

find

- 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다.노드 a가 a ∈ A 일 때 find(a)는 A 집합의 대표 노드를 반환한다.

 

구현 방법

일반적으로 1차원 배열을 이용해 각 노드가 속한 집합에서의 대표 노드를 저장한다.

1~6의 값을 가지고 있는 노드들이 있다. 현재 연결된 노드가 없으므로 모든 집합의 대표 노드는 자기 자신이 된다.

 

union(1, 4)와 union(5, 6)을 수행하면 아래와 같이 배열의 값이 업데이트 된다. 

{1, 4} 집합에서 대표 노드는 4일 수도 있고, {5, 6} 집합에서 대표 노드는 6일수도 있지만 통일성을 주기 위해 각 집합의 대표 노드는 최솟값을 가지는 노드라고 하겠다.

 

여기서 union(4, 6)을 수행했을 때, 위에서 설명한 것과 같이 생각해보면 각 집합의 대표 노드는 최솟값을 가지는 노드이고 {1, 4}와 {5, 6}을 합쳤을 때 최솟값을 가지는 노드는 1이기 때문에 해당 배열의 값을 전부 1로 변경해야 된다. 하지만 만약 각 집합의 개수가 10억개라면 10억개의 배열을 모두 업데이트 해줘야하기 때문에 비효율적인 방법이다. 따라서, union 연산을 수행할 때 해당 집합의 모든 원소의 배열 값을 업데이트 하는 것이 아니라 대표 노드의 배열 값만 업데이트 해준다. 각 집합의 대표 노드를 찾기 위해서는 find 연산을 수행하면 된다.

여기서 6이 속한 집합의 대표 노드는 계산 했을 때 1이 나와야 한다. 배열이 가리키는 노드들을 쭉 따라가다가 자기 자신이 대표 노드인 곳에서 멈추면 찾을 수 있다. 대표 노드 배열을 parent라고 할 때 아래와 같이 수행된다.

parent[6] = 5 -> parent[5] = 1 -> parent[1] = 1 (자기 자신이 대표 노드인 경우)

 

코드

union

각 집합의 대표 노드를 찾아서 연결해주면 된다.

public void union(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    
    parent[pb] = pa;
}

 

연결할 때 통일성을 주기 위해 아래와 같이 작성해도 된다.

public void union(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    
    if (pa < pb) {
    	parent[pb] = pa;
    } else {
    	parent[pa] = pb;
    }
}

 

find

public int find(int idx) {
    if (parent[idx] == idx) {
        return idx;
    }
    
    return parent[idx] = find(parent[idx]);
}

거슬러 올라가면서 스쳐지나가는 노드들의 대표 노드 값도 바꿔주기 위해 return 값에서 대입하는 연산도 함께 해준다.