🔥, [Swift/Algorithm] 분리 집합(Disjoint Set)과 유니온 파인드(Union-Find) 알고리즘

1. 분리 집합(Disjoint Set)

서로소 집합이라고 불리우는 분리 집합은 중복되는 부분이 발생하지 않도록 모든 원소를 분리한 집합을 말한다. 그냥 서로 중복되지 않는 부분 집합들로 이루어진 원소들에 대해 저장하고 있는 자료구조이다.

전체 집합 U에 대해, U의 분리 집합 A와 B는 다음과 같은 조건들을 만족한다.
- A, B는 U의 부분 집합이다.
- A, B는 공통 원소를 가지지 않는다.
- A, B의 합 집합이 전체 집합 U이다. (A, B 둘 다 속하지 않는 U의 원소가 없어야 한다.)

2. 유니온 파인드(Union-Find)

유니온 파인드는 분리 집합을 구현하는 알고리즘으로, 트리 구조로 표현하는 것이 가장 효율적이(라고 한)다.

먼저, 각 노드 별로 부모 노드 번호를 기록한다. 그럼 그래프가 트리 형태로 표현된다.

최상위 노드인 root 노드라면 부모 노드의 번호는 자기 자신의 번호이다.
- 이 root 노드로 그룹을 구별할 수 있다.
각 노드가 같은 그룹인지 확인하는 것을 DFS 등의 탐색을 거치지 않고, 부모 노드가 일치하는지로 판별하는 것이다.
한 노드의 그룹과 다른 한 노드의 그룹이 합쳐진다면, 부모 노드 번호를 다른 한 노드의 부모 노드로 지정하는 식으로 트리를 병합할 수 있다.

(1) makeSet(x)

초기화 작업. x를 유일한 원소로 하는 새로운 집합을 만든다.

var parent = Array(0...n)

0에서 n까지의 노드에 대한 부모 노드 번호를 기록한 배열을 초기화한다.

(2) find(x)

x가 속한 집합의 대표 값인 root 노드를 반환한다. 즉, x가 어떤 집합, 어떤 그룹에에 속해 있는지 찾는다.

func find(_ x: Int) -> Int {
    if x == parent[x] {
        return x // 루트 노드는 부모 노드 번호가 자기 자신의 번호이다. 따라서 루트 노드이므로 리턴
    } else {
        return parent[x] // 부모 노드로 거슬러 올라가는 중........
    }
}

재귀를 이용하여 부모 노드를 찾는다.
부모 노드의 번호가 자기 자신의 번호라면 여기는 root 노드입니다..리턴한다.
재귀를 이용해서 부모 노드로 거슬러 올라간다.

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

경로 압축(Path Compression)을 통한 최적화 코드이다.
하나의 노드에 대해 find 연산을 할 때마다 그 노드의 부모 노드를 항상 root 노드로 만들어준다면, root 노드를 찾아 거슬러 올라갈 필요가 없어진다. find 연산 시 중복되는 연산들을 줄여주기 때문에 더 효율적으로 root 노드를 찾을 수 있(다고 한)다.

(3) union(x, y)

x가 속한 집합과 y가 속한 집합을 합친다. 즉, 두 개의 트리를 병합한다.

func union(_ x: Int, _ y: Int) {
    let rootX = find(x)
    let rootY = find(y)
    
    if rootX != rootY {
        parent[rootX] = rootY
    }
}

x, y 각각 최상위 root 노드 rootX, rootY를 find 연산을 통해서 찾는다.
만약 root 노드가 다르다면, 이는 서로 다른 트리 그룹이므로, 한 쪽의 트리를 다른 한 쪽에 붙인다. 한 쪽의 root 노드의 부모 노드를 다른 한 쪽으로 등록하면 된다.

var rank = [Int](repeating: 0, count: n + 1)

func union(_ x: Int, _ y: Int) {
    var rootX = find(x)
    var rootY = find(y)
    
    if rootX != rootY {
        if rank[rootX] < rank[rootY] {
            parent[rootX] = rootY // 높이가 낮으면(작으면) 높이가 높은 데에 붙인다(부모 노드로 등록)
        } else rank[rootX] > rank[rootY] {
            parent[rootY] = rootX // 트리의 높이가 높은 쪽이 루트가 되는 셈
        } else {
		        parent[rootX] = rootY // 높이가 같으면 일단 x의 부모를 y로 설정해서 트리를 합치고
            rank[rootX] += 1 // 합친 트리의 높이 1 증가
        }
    }
}

트리의 높이를 통해 최적화한 코드이다.
find의 시간 복잡도는 트리의 높이에 의해 결정된다. 이때, union 연산할 때 항상 높이가 낮은 트리를 높이가 높은 트리에 붙여서 시간 복잡도를 줄일 수 있다. 높이가 낮은 트리를 높은 트리에 붙여야 합쳐진 트리의 높이가 덜 증가한다..
따라서 트리의 높이를 기록한 rank 배열을 별도로 만들어놓고, 비교하면서

3. PS 문제 목록

[x] [백준/골5] 집합의 표현 https://www.acmicpc.net/problem/1717
[ ] [백준/골2] 친구 네트워크 https://www.acmicpc.net/problem/4195
[ ] [백준/골4] 거짓말 https://www.acmicpc.net/problem/1043
[ ] [백준/골3] 개구리 점프 https://www.acmicpc.net/problem/17619
[ ] [백준/골4] 여행 가자 https://www.acmicpc.net/problem/1976
[ ] [프로그래머스/Lv.4] 호텔 방 배정 https://school.programmers.co.kr/learn/courses/30/lessons/64063
[ ] https://www.acmicpc.net/workbook/view/6784

[Swift/Algorithm] 분리 집합(Disjoint Set)과 유니온 파인드(Union-Find) 알고리즘