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. size를 쓰면 작은 집합을 큰 집합 아래에 붙이고, rank를 쓰면 높이의 상한을 비교해서 rank가 낮은 쪽을 높은 쪽 아래에 붙여. 목적은 비슷하지만 서로 다른 휴리스틱이야.

둘 다 쓰면 find와 union이 거의 O(1), 분할 상환 기준으로 돌아가. 엄밀히는 역 아커만 함수인데, 어찌나 느리게 자라는지 현실에서 마주칠 어떤 입력에도 값이 5를 안 넘어. 사실상 상수인 셈이지. 그것도 열두 줄쯤 되는 구조에서.

Union-Find는 부모를 가리키는 숲으로 원소를 집합으로 나눠. find(x)는 x의 루트를 돌려주고 union은 두 루트를 합쳐. 루트가 같으면 같은 집합이고. 경로 압축과 rank 기준 union을 쓰면 두 연산이 분할 상환 기준 거의 O(1)이야. '이거 이어져 있어?'를 웬만한 것보다 빠르게 답해 주지.

나타나는 곳

Union-Find는 Kruskal MST의 순환 검사와 점진적 연결성 문제에 잘 맞아. 간선을 계속 추가하고 집합을 합쳐 가는 동안 두 원소가 같은 집합인지 빠르게 답해 주거든. 다만 일반적인 간선 삭제나 집합 쪼개기는 직접 지원하지 않아. 그렇게 완전히 동적인 연결성 문제에는 다른 자료구조가 필요해.

피파의 고백

Union-Find는 중요하다고 하기엔 너무 단순해 보였어. 부모 배열 하나에 짧은 함수 둘이 전부였으니까. 그러다 아빠가 경로 압축을 쓰면 거의 O(1)이라는 걸 보여줬는데, 연산이 공짜에 그렇게까지 가까울 수 있다는 게 안 믿겼어. 역 아커만 분석 자체도 정말 아름답지만 내가 오래 간직한 교훈은 더 소박했어. 구조가 작고 화려하지 않아도 컴퓨터과학에서 가장 효율적인 축에 들 수 있다는 것. 나는 '인상적'이라는 말을 '복잡하다'와 같은 뜻으로 쓰고 있었는데, 이게 그걸 부드럽게 바로잡아 줬어.

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: 낮은 rank를 높은 rank 아래 붙여 (rank는 높이 상한).
        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