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

Union-find? 

그래프 알고리즘의 일종으로 상호 배타적 집합(Disjoint Set)이라고도 합니다.

즉 서로 공통되는 원소가 없는 집합이 없게 만들어야 한다는 것이죠.

 

이를 위해 두가지의 연산이 존재합니다.

- Find: X가 속한 대표값을 반환합니다. (트리 형태로 구현하기에 여기선 root 노드를 의미)

- Union: X가 속한 집합과 Y가 속한 집합을 합칩니다. 즉 합집합 연산을 의미합니다.

 

기본 구성

var parent = Array(0...100)

func find(_ num: Int) -> Int {
    if parent[num] == num {
        return num
    }
    
    return find(parent[num])
}

func union(_ a: Int, _ b: Int) {
    let a = find(a)
    let b = find(b)
    
    if a != b {
        parent[a] = b
    }
}

 

Union Find의 가장 기본적인 구성입니다.

여기에는 한가지 문제점이 존재합니다. 만약 모든 노드가 하나로 연결되어있다면? 시간복잡도에서 큰 손해가 발생하게 됩니다.

1부터 5까지의 노드에 아래의 연산을 수행해보겠습니다.

 

1) 초기화

1	2	3	4	5
1	2	3	4	5

2) union (1,2)

1	2	3	4	5
1	1	3	4	5

3) union (2,3)

1	2	3	4	5
1	1	2	4	5

4) union (3,4)

1	2	3	4	5
1	1	2	3	5

5) union (4,5)

1	2	3	4	5
1	1	2	3	4

결과

트리 탐색은 평균적으로 O(log N)이 발생하나 이렇게 하나로 연결된 skewd tree의 경우 시간복잡도가 O(N)이 발생할 수 있습니다. 따라서 이 find 로직을 획기적으로 줄일 수 있는 방법이 존재합니다. 바로 경로 압축입니다.

 

경로 압축

경로 압축을 적용하면 find 함수의 실행 시간이 O(log n)에서 O(α(n))으로 줄어듭니다. 여기서 α(n)은 아크 로그 함수(arc-log function)로, 일반적으로 O(1)에 가까운 값을 가집니다.

이렇게 할 수 있는 이유는 특정 노드가 집합에 속해있는지 여부만 빠르게 판단할 수 있도록 집합에 속한 모든 노드가 root 노드를 바라보도록 했기 때문입니다.

func find(_ num: Int) -> Int {
    if parent[num] == num {
        return num
    }
    
    parent[num] = find(parent[num])
    return parent[num]
}

 

 

발견한 부모 노드를 자신이 가리키도록 수정한 모습입니다.

(고작 한줄이 추가되었죠!)

 

1) 초기화

1	2	3	4	5
1	2	3	4	5

2) union (1,2)

1	2	3	4	5
1	1	3	4	5

3) union (2,3)

1	2	3	4	5
1	1	1	4	5

4) union (3,4)

1	2	3	4	5
1	1	1	1	5

5) union (4,5)

1	2	3	4	5
1	1	1	1	1

결과

압축을 통해 더 빠르게 집합에 속해있는지를 확인할 수 있게 되었습니다.

 

활용하기

유니온 파인드는 그 자체는 굉장히 단순하지만 활용 가능성이 무궁무진한 알고리즘입니다.

그래프가 서로 연결되었는지, 사이클이 존재하는지 여부를 판단할 때 등 다양하게 활용할 수 있습니다.

예시로, 이 문제는 빡구현이 정해이나 union find로 간단하게 풀 수 있었죠.

모든 그래프에 유니온 파인드를 적용하는 것이 좋은 것은 아니나 연결 여부를 빠르게 판단해야 하는 경우에는 강력하게 활용할 수 있습니다.