[Algorithm] - 유니온 파인드(Union-Find)(swift)

 

백준 문제를 풀다가 유니온 파인드라는 알고리즘을 고맙게도 알게 되었다.

 

1717번: 집합의 표현

 

 

---

Union-Find

 

 

• 두 노드가 서로 같은 그래프에 속하는 지 판단
• Disjoint-Set / 서로소 집합 알고리즘이라고도 불린다.
• 주로 그래프 이론과 연결 요소 찾는 데 활용

 

 

---

 

Union-Find는 다음 두 연산을 지원한다.

 

• Find() : 특정 원소가 속한 집합을 찾는다. 즉, 어떤 원소가 어떤 집합에 속해 있는 지를 확인하는 연산
• Union() : 두 집합을 하나로 합친다. 즉, 두 원소가 속한 집합을 합치는 연산

 

https://dev-mandos.tistory.com/296 에서 예제를 참고하였습니다.

 

아래 이미지에서 1과 6이 같은 그래프에 있는지 확인해보자.

 

 

1️⃣ Find()

 

Find()를 통해 부모노드를 찾아보자.

 

"parent[2] = 1 의 의미는 2번 노드의 부모는 1"이라는 의미이다.

 

위의 이미지를 parent 배열에 나타내보자.

i	1	2	3	4	5	6
parent	1	1	2	3	5	5

 

 

🔎 find 연산이 동작하는 과정

 

4의 부모노드를 찾아보자.

4->3->2->1 순으로 부모노드를 타고 올라가 최종적으로 1에 도달하게 된다.

그렇기 때문에 4의 부모노드는 1이다.

 

4의 부모노드를 찾은 후의 parent 배열을 확인해보자.

 

• parent = [1, 1, 2, 3, 5, 5]

parent 배열이 처음과 바뀐 것이 없다. find(4) = 1이라는 것을 알았으니 3, 4의 parent 배열을 1로 바꿔줘야 한다.

1로 바꾸지 않으면 처음과 같이 4->3->2->1 순으로 부모노드를 찾아야 한다.

 

3, 4의 부모노드를 1로 바꾼다면 4->1로 바로 종료가 된다.

 

// 특정 원소가 속한 집합을 찾음
func find(_ x: Int) -> Int {
    if parent[x] != x {
        // 부모 노드가 자기 자신이 아니라면, 재귀적으로 부모를 찾음
        parent[x] = find(parent[x])
    }
    return parent[x]
}

 

 

다음과 같이 그래프를 변경할 수 있다.

 

i	1	2	3	4	5	6
parent	1	1	1	1	5	5

 

 

 

 

2️⃣ Union()

 

합집합의 역할을 하는 Union 연산에 대해 알아보자.

 

두 원소가 속한 집합을 합치는 연산이기 때문에 A와 B 노드가 있다면, 둘 중 한 부모 노드를 다른 노드의 자식 노드로 넣어주면 된다.

 

위의 예제에서 4번 노드와 6번 노드를 합쳐보자.

둘 중 한 부모 노드를 다른 노드의 자식 노드로 넣어주면 되니까 4의 부모 노드인 1을, 6의 부모 노드인 5번 노드의 자식으로 넣으면 된다.

 

다음과 같이 만들어진다.

 

// 두 원소가 속한 집합을 합침
    func union(_ a: Int, _ b: Int) {
        let rootA = find(a)
        let rootB = find(b)

        parent[rootA] = rootB
    }