[Algorithm] Union-Find 알고리즘 (Swift)

Union-Find 알고리즘 이란?

서로소 집합(Disjoint Set)을 효율적으로 관리하는 알고리즘이다. 아래의 두 그래프는 서로소인 집합이라고 볼 수 있다. 아래의 그래프가 주어진다면 1과 6은 같은 그룹에 속해있는지 판별할 수 있는지, 어떻게 주어진 자료로 아래의 그룹을 만들지 결정하는 알고리즘이다.

알고리즘 구현하기

Find

재귀함수를 활용하여 부모를 찾는다. 4의 경우에는 2를 타고 가서 1이 root 로 나오게 된다.

 

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

 

Union

아래의 노드들을 그래프로 묶는 roots 배열을 만드는 것이 union 이다.

func union(_ a: Int, _ b: Int) {
    let rootA = find(a)
    let rootB = find(b)
    
    roots[rootA] = rootB
}

 

예를 들면 아래와 같이 연결 배열이 나오게 된다면 아래와 같이 두 그룹으로 나눌 수 있게 된다.

let links = [(2, 1), (3, 1), (4, 2), (5, 1), (7, 6), (8, 6)]

for link in links {
    union(link.0, link.1)
}

print(roots) // [0, 1, 1, 1, 1, 1, 6, 6, 6]

 

이 개념을 활용하여 다양하게 그룹을 지을 수 있고, 루트를 쉽게 찾을 수 있다. union 을 하는 방법도 여러 조건에 따라 해 줄 수 있어서 상황이나 문제별로 달라지는 것 같다.