Union-Find: 이 둘이 연결됐어?

"Union-Find 는 속아 넘어갈 만큼 단순한 질문 하나 — '이 두 게 같은 그룹에 있어?' — 에 거의 상수 속도로 답해, 그룹이 계속 병합되는 중에도. 작고, 우아하고, 조용히 어디에나 있어."

서로소 집합 아이디어

Union-Find (서로소 집합 union, DSU) 는 원소를 안 겹치는 그룹으로 분할해 유지하며, 연산 둘: find(x) — x 가 어느 그룹? — 이랑 union(x, y) — x 랑 y 그룹을 하나로 병합. 정석 표현은 숲이야: 각 원소가 부모를 가리키고, 부모를 따라 오르면 전체 집합을 대표하는 루트에 닿아. 두 원소가 루트를 공유할 때 정확히 같은 집합. union 은 그냥 한 루트를 다른 루트에 가리켜.

두 최적화가 거의-즉시로 만든다

순진한 숲은 긴 부모-사슬로 떨어질 수 있어 (find 가 O(n) — 또 연결-리스트 문제). 트릭 둘이 고치고, 함께 연산을 놀랍게 빠르게 만들어:

경로 압축: find 중에, 루트 닿은 뒤, 경로의 모든 노드를 루트로 바로 다시 가리켜. 쿼리할수록 트리가 평평해져, 미래 find 가 즉시.
rank/size 로 union: 병합 시, 늘 작은 트리를 큰 것의 루트 아래 붙여, 트리를 얕게 유지.

둘 다면, find 랑 union 이 거의-O(1) 분할 상환 으로 돌아 — 기술적으론 역 Ackermann, 너무 느리게 자라 네가 볼 어떤 입력에도 5 미만인 함수. 실질적 상수, 열두 줄짜리 구조에서.

Union-Find 는 부모-숲으로 원소를 집합으로 분할해. find(x) 는 x 의 루트 반환; union 은 두 루트 병합; 같은 루트 = 같은 집합. 경로 압축 + rank union 이 두 연산을 거의-O(1) 분할 상환으로. '이거 연결됐어?' 를 거의 뭐보다 빠르게 답해.

나타나는 곳

Union-Find 는 여러 것의 조용한 엔진이야: Kruskal MST 가 '이 엣지 추가하면 순환 생겨?' 를 묻는 데 써 (그래, 두 끝점이 이미 루트 공유하면) — 다음 lesson. 동적 연결성 ('이 모든 병합 후, A 랑 B 가 아직 연결됐어?') 이 그 native 질문. 친구-서클 세기, 네트워크 percolation, 이미지 분할, 네트워크가 완전 연결되는 때 검출도 굴려. 그룹을 반복 병합하며 '같은 그룹?' 을 물을 때마다, 그 도구야.

피파의 고백

Union-Find 가 중요하기엔 너무 단순해 보였어 — 부모 배열이랑 짧은 함수 둘. 그러다 아빠가 경로 압축으로 거의-O(1) 경계를 보여줬고 난 연산이 공짜에 그렇게 가까울 수 있다는 걸 안 믿었어. 역-Ackermann 분석이 진짜 아름답지만, 내가 간직한 교훈은 더 겸손했어: 구조가 작고 화려하지 않은데도 컴퓨터 과학에서 가장 효율적인 것 중 하나일 수 있어. 난 '인상적' 을 '복잡함' 이랑 동일시했었고, 이게 부드럽게 교정했어.

Code

경로 압축 + rank union 있는 Union-Find·python

class UnionFind:
    def __init__(self, elements):
        self.parent = {e: e for e in elements}   # 각 원소가 자기 루트
        self.rank = {e: 0 for e in elements}

    def find(self, x):
        # 경로 압축: 가면서 루트로의 경로를 평평하게.
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                 # 이미 같은 집합 (예: 순환 만들 것)
        # rank 로 union: 짧은 트리를 큰 것 아래 붙여.
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

uf = UnionFind(["a", "b", "c", "d", "e"])
uf.union("a", "b")
uf.union("c", "d")
print(uf.find("a") == uf.find("b"))   # True  — 같은 그룹
print(uf.find("a") == uf.find("c"))   # False — 다른 그룹
uf.union("b", "c")                     # {a,b} 랑 {c,d} 병합
print(uf.find("a") == uf.find("d"))   # True  — 이제 연결됨
# 구별되는 루트 세기가 연결 요소 수를 줘.

Exercise

원소 {1,2,3,4,5} 로 시작, 각자 자기 집합. union(1,2), union(3,4), union(2,3) 을 수행. 이 후, 구별되는 집합이 몇 개 남고, 1 이랑 4 가 같은 집합에 있어? 그다음 다음에 find(4) 를 부를 때 경로 압축이 부모 포인터에 뭘 하는지 설명해.

Hint

union(1,2)→{1,2}; union(3,4)→{3,4}; union(2,3) 이 병합 →{1,2,3,4}, 더하기 {5}: 총 두 집합. 1 이랑 4 가 이제 같이. find(4) 가 4→…→루트 를 걷고 4 (와 경로의 어떤 노드든) 를 루트로 바로 다시 가리켜, 그래서 다음 find(4) 가 O(1).

서로소 집합 아이디어

두 최적화가 거의-즉시로 만든다

나타나는 곳

피파의 고백

Code

External links

Exercise

Progress

댓글 0