유니온 파인드 - 같은 그룹인가

이 장에서 배우는 것

친구 관계를 하나씩 추가할 때마다 두 사람이 같은 그룹에 속하는지 알고 싶다고 하자. 앞 장에서 배운 탐색으로도 답할 수 있다. 다만 관계가 추가될 때마다 그래프를 다시 탐색하면 이미 확인한 연결을 거듭 따라가게 된다. 이번에는 각 사람이 어느 그룹을 대표하는 사람에게 이어지는지만 저장한다. 그룹을 합치고 대표를 찾는 두 연산으로 연결 여부를 관리하는 자료구조를 직접 만든다.

서로 겹치지 않는 그룹들의 모음을 전공 수업에서는 서로소 집합이라 부른다. 이를 효율적으로 관리하는 대표적인 구현이 유니온 파인드(Union-Find)다. 이름에서 합치기는 두 그룹을 하나로 만드는 연산이고, 찾기는 원소가 속한 그룹의 대표를 구하는 연산이다. 여기서 찾는 대상은 배열에 들어 있는 값 자체가 아니라 그룹의 대표라는 점에 주의한다.

• 부모 배열로 여러 그룹을 표현하고 대표를 찾는다.
• 경로 압축과 랭크 합치기가 부모 연결을 어떻게 바꾸는지 확인한다.
• 부모 이동과 부모 변경 횟수를 세어 시간 복잡도의 의미를 살핀다.
• 연결 요소와 크루스칼 알고리즘에 같은 연산을 적용한다.
• 직접 만든 구현과 내장 집합으로 만든 비교 구현의 결과를 대조한다.

문제 상황

작은 협업 서비스에서 사용자가 친구 관계를 등록한다고 하자. 친구 관계를 따라 여러 단계를 거쳐 도달할 수 있는 사람들을 하나의 그룹으로 취급한다. 가람과 나래가 친구이고 나래와 다온이 친구라면, 가람과 다온도 같은 그룹이다. 서로 직접 친구인지와 같은 그룹인지는 다른 질문이다.

등록 요청은 시간 순서대로 들어온다. 이미 같은 그룹에 속한 두 사람의 관계가 다시 등록될 수도 있다. 서비스가 알아야 할 것은 새 요청이 그룹 수를 줄였는지, 그리고 현재 두 사람이 같은 그룹인지다. 친구를 끊는 기능은 이번 요구사항에 없다.

사람마다 정수 번호를 하나 부여하면 문자열을 비교하는 문제와 그룹을 관리하는 문제를 분리할 수 있다. 완성 코드에서는 여덟 사람에게 0부터 7까지 번호를 붙인다. 이름은 화면에 보여 주는 용도로만 사용하며, 내부 저장은 생성할 때 크기가 정해지는 리스트를 배열처럼 사용한다. 원소를 덧붙이거나 중간에서 지우지 않는다.

이 구조는 친구 관계 전체를 보관하지 않는다. 따라서 누가 누구와 직접 친구인지, 두 사람 사이에 어떤 경로가 있는지는 답하지 못한다. 대신 관계가 추가되는 상황에서 같은 그룹인지 반복해서 묻는 요구에 집중한다. 자료구조를 만든다는 것은 필요한 질문을 빠르게 답할 수 있도록 저장할 정보를 고르는 일이기도 하다.

부모 배열로 그룹을 나타낸다

각 번호에 부모 번호를 하나씩 저장한다. 부모를 따라갔을 때 자기 자신을 부모로 가진 번호가 나오면 거기서 멈춘다. 이 번호가 그룹의 대표다. 부모가 자기 자신인 노드를 전공 수업에서는 루트(root)라 부른다. 노드는 여기서 사람 한 명에 해당한다.

처음에는 모두 혼자이므로 parent[i] = i다. 0과 1을 합칠 때 1의 부모를 0으로 바꾸면 두 번호의 대표가 모두 0이 된다. 이후 2와 3의 그룹을 이 그룹에 붙일 때는 대표 2의 부모만 0으로 바꾸면 된다. 3의 부모를 당장 바꾸지 않아도 3 → 2 → 0을 따라 같은 대표에 도달한다.

부모 연결들은 순환하지 않는 여러 나무 모양을 이룬다. 이런 여러 트리의 모음을 전공 수업에서는 포리스트(forest)라 부른다. 여기서 트리는 실제 친구 관계를 그린 그림이 아니다. 합치기 과정에서 만든 관리용 연결이다. 대표끼리 연결한다는 규칙을 지켜야 이 모양을 유지할 수 있다.

부모 배열이 유지해야 하는 규칙

항목	의미	확인 방법
parent[i]	i의 부모 번호	0 이상 원소 수 미만이다.
parent[r] = r	r이 대표다.	부모를 따라가다 여기서 멈춘다.
대표가 같다	같은 그룹이다.	find(a)와 find(b)를 비교한다.
대표끼리 연결한다	두 그룹 전체를 합친다.	union 안에서 먼저 find를 호출한다.

대표 번호에 업무 의미를 부여해서는 안 된다. 가장 먼저 가입한 사람이나 이름순으로 앞선 사람을 뜻하지 않는다. 이번 구현의 규칙과 입력 순서가 정한 번호일 뿐이다. 표시할 그룹 이름이 필요하다면 대표와 별도로 관리해야 한다.

최적화 없이 부모만 이어 붙이면 긴 사슬이 생길 수 있다. 원소 수를 n이라 할 때 가장 먼 원소에서 대표까지 n − 1번 이동할 수도 있다. 이때 찾기의 최악 시간 복잡도는 O(n)이다. 시간 복잡도는 입력 크기가 커질 때 작업량이 어떻게 증가하는지 나타내는 표기다. 이번에는 실제 부모 이동 횟수로 그 작업량을 관찰한다.

경로를 줄이고 낮은 트리를 붙인다

찾은 대표를 부모로 다시 저장한다

3 → 2 → 0을 따라 대표 0을 찾았다고 하자. 다음에도 같은 길을 걸을 필요는 없다. 3의 부모를 0으로 바꾸면 이후에는 한 번만 이동한다. 찾는 과정에서 거친 원소들이 대표를 직접 가리키도록 바꾸는 방법을 전공 수업에서는 경로 압축(path compression)이라 부른다.

완성 코드에서는 반복문 두 개를 사용한다. 첫 번째 반복문은 부모를 따라 대표까지 간다. 두 번째 반복문은 출발점으로 돌아와 그 길의 부모를 대표로 바꾼다. 부모를 덮어쓰기 전에 기존 부모를 임시 변수에 저장해야 다음 원소로 이동할 수 있다. 재귀 호출을 사용하지 않으므로 호출 깊이 제한에 의존하지 않는다.

찾기는 질문에 답하면서 내부 배열도 바꾼다. 하지만 같은 그룹인지에 대한 답은 바뀌지 않는다. 연결을 새로 만들거나 그룹을 쪼개는 것이 아니라, 이미 도달할 수 있던 대표로 가는 길만 줄이기 때문이다. 따라서 출력용 그룹 목록을 만드는 찾기 호출도 연산 횟수에 포함해야 측정 범위가 분명해진다.

랭크는 합칠 방향을 결정한다

경로 압축은 이미 길어진 경로를 줄인다. 합칠 때부터 경로가 과하게 길어지는 것을 줄이는 규칙도 필요하다. 각 대표에 트리 높이를 관리하기 위한 정수를 붙이며, 이를 전공 수업에서는 랭크(rank)라 부른다. 처음 랭크는 모두 0이다.

두 대표의 랭크가 다르면 작은 쪽을 큰 쪽 밑에 붙인다. 랭크가 같으면 한쪽을 다른 쪽에 붙이고, 남은 대표의 랭크만 1 증가시킨다. 완성 코드에서는 랭크가 같을 때 첫 번째 대표를 남겨 결과를 결정적으로 만든다.

경로 압축 뒤에는 실제 높이가 낮아질 수 있지만 랭크는 줄이지 않는다. 따라서 랭크는 현재 높이의 정확한 측정값이 아니다. 합칠 방향을 고르는 데 쓰는 높이의 상한으로 이해하면 된다. 루트가 아닌 원소의 랭크 값은 합칠 방향을 결정할 때 읽지 않는다.

랭크가 r인 대표가 만들어지려면 그 그룹에는 적어도 2의 r제곱 개의 원소가 필요하다. 같은 랭크끼리 합칠 때만 랭크가 증가하기 때문이다. 따라서 랭크 합치기만 사용해도 높이는 O(log n)으로 제한된다. 경로 압축까지 함께 사용하면 여러 연산 전체의 비용을 더 낮출 수 있다.

초기화 이후 m번의 찾기와 합치기를 수행하는 전체 비용의 표준적인 상한은 O(m α(n))이다. α는 역 아커만 함수라 부르는, 매우 느리게 증가하는 함수다. 전체 비용을 연산 수로 나누어 해석하는 방식을 전공 수업에서는 분할 상환 분석이라 부른다. 한 번의 찾기가 항상 한 번의 부모 이동으로 끝난다는 뜻은 아니다. 초기화 비용 O(n)은 따로 더한다.

연결 요소와 크루스칼에 적용한다

방향이 없는 그래프에서 서로 경로로 이어지는 정점들의 최대 묶음을 전공 수업에서는 연결 요소(connected component)라 부른다. 모든 정점을 따로 시작한 뒤 각 간선의 양 끝을 합치면, 마지막 그룹들이 연결 요소가 된다. 그래프를 모두 저장하지 않고 간선을 하나씩 처리해도 된다.

처음 연결 요소 수는 정점 수와 같다. 서로 다른 대표를 합쳤을 때만 1을 뺀다. 이미 같은 대표라면 새 간선이 들어와도 요소 수는 그대로다. 완성 코드의 union은 실제로 두 그룹을 합쳤으면 True, 이미 같은 그룹이면 False를 돌려준다.

방향 없는 그래프에서 간선의 양 끝이 이미 같은 그룹이라면 그 간선을 추가할 때 순환이 생긴다. 전공 수업에서는 이를 사이클(cycle)이라 부른다. 이 성질은 모든 정점을 잇는 데 드는 비용을 줄이는 문제에도 쓰인다.

간선에 비용이 있고 모든 정점을 연결하면서 순환이 없도록 고른 트리를 신장 트리라 부른다. 그중 비용 합이 가장 작은 것이 최소 신장 트리다. 크루스칼 알고리즘(Kruskal algorithm)은 간선을 비용이 작은 순서대로 살피며 서로 다른 그룹을 잇는 간선만 선택한다.

현재 그룹들을 가르는 간선 중 가장 싼 간선을 선택하면, 어떤 최소 신장 트리의 더 비싼 연결을 그 간선으로 교체할 수 있다. 이것이 작은 비용부터 선택하는 근거다. 유니온 파인드는 그 선택에서 순환이 생기는지를 빠르게 판단하는 역할을 맡는다. 비용 순서를 정하는 일까지 대신하지는 않는다.

완성 코드의 작은 예제는 비용순으로 준비된 고정 배열을 사용한다. 비용 1과 2인 간선을 고르면 0, 1, 2가 이어진다. 비용 3인 간선은 이미 이어진 0과 2를 잇기 때문에 제외한다. 비용 4인 간선으로 3을 붙이면 세 간선의 비용 합은 7이다. 일반 입력에서는 간선 정렬 비용 O(E log E)와 그룹 연산 비용을 함께 고려해야 한다. E는 간선 수다.

그래프가 처음부터 연결되어 있지 않다면 모든 정점을 잇는 트리가 나오지 않는다. 선택한 간선 수가 정점 수 − 1인지 확인해야 한다. 이번 예제는 정점 네 개가 모두 연결되는 입력을 사용한다.

완성 코드

다음 내용을 main.py에 저장한다. 직접 구현하는 부분에서는 고정 크기 리스트만 내부 배열로 사용한다. 마지막 비교용 클래스에 한해서 내장 딕셔너리와 집합을 사용한다. 외부 패키지, 파일 입력, 난수는 사용하지 않는다.

부모 이동은 대표를 찾는 첫 순회의 간선 이동 수다. 부모 변경은 합칠 때 루트를 붙이거나 경로 압축으로 기존 부모와 다른 값을 저장한 횟수다. 두 번째 순회의 방문 횟수도 첫 순회와 같지만 부모 이동 지표에 중복해서 더하지 않는다. 따라서 출력 숫자는 전체 파이썬 명령 수나 실행 시간이 아니다.

class UnionFind:
    # [1] 고정 크기 배열과 측정값
    def __init__(self, size, compress=True):
        if size < 0:
            raise ValueError("크기는 음수일 수 없다")
        self.parent = [0] * size
        self.rank = [0] * size
        for i in range(size):
            self.parent[i] = i
        self.components = size
        self.compress = compress
        self.find_calls = 0
        self.parent_steps = 0
        self.parent_writes = 0
        self.union_calls = 0
        self.merges = 0

    def _check(self, x):
        if x < 0 or x >= len(self.parent):
            raise IndexError("원소 번호가 범위를 벗어났다")

    # [2] 대표 찾기와 선택적 경로 압축
    def find(self, x):
        self._check(x)
        self.find_calls += 1
        root = x
        while self.parent[root] != root:
            self.parent_steps += 1
            root = self.parent[root]

        if self.compress:
            current = x
            while self.parent[current] != current:
                next_node = self.parent[current]
                if self.parent[current] != root:
                    self.parent[current] = root
                    self.parent_writes += 1
                current = next_node
        return root

    # [3] 대표의 랭크를 비교해 합치기
    def union(self, a, b):
        self._check(a)
        self._check(b)
        self.union_calls += 1
        ra = self.find(a)
        rb = self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.parent_writes += 1
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.components -= 1
        self.merges += 1
        return True

    def same(self, a, b):
        self._check(a)
        self._check(b)
        return self.find(a) == self.find(b)


class BuiltinGroups:
    # [4] 비교 전용: 각 번호가 자신이 속한 집합을 가리킨다.
    def __init__(self, size):
        self.groups = {}
        for i in range(size):
            self.groups[i] = {i}
        self.membership_checks = 0
        self.member_moves = 0

    def union(self, a, b):
        self.membership_checks += 1
        left = self.groups[a]
        right = self.groups[b]
        if b in left:
            return False
        for member in right:
            left.add(member)
            self.groups[member] = left
            self.member_moves += 1
        return True

    def same(self, a, b):
        self.membership_checks += 1
        return b in self.groups[a]


def run_friends():
    # [5] 관계와 질의는 고정 입력이다.
    names = ("가람", "나래", "다온", "라온",
             "마루", "바다", "새봄", "아람")
    relations = (
        (0, 1), (2, 3), (0, 2),
        (4, 5), (6, 7), (4, 6),
        (1, 3), (5, 7),
    )
    queries = ((0, 3), (0, 7), (4, 7))
    size = len(names)
    fast = UnionFind(size)
    plain = UnionFind(size, compress=False)
    reference = BuiltinGroups(size)

    for a, b in relations:
        merged = fast.union(a, b)
        assert plain.union(a, b) == merged
        assert reference.union(a, b) == merged

    print("친구 그룹 확인")
    for a, b in queries:
        answer = fast.same(a, b)
        assert plain.same(a, b) == answer
        assert reference.same(a, b) == answer
        word = "같다" if answer else "다르다"
        print(f"{names[a]} / {names[b]}: {word}")

    # [6] 출력용 찾기도 두 구현에서 똑같이 수행한다.
    labels = [0] * size
    for i in range(size):
        labels[i] = fast.find(i)
        assert plain.find(i) == labels[i]

    print(f"그룹 수: {fast.components}")
    for root in range(size):
        if labels[root] != root:
            continue
        line = ""
        for i in range(size):
            if labels[i] == root:
                if line:
                    line += ", "
                line += names[i]
        print(f"그룹 {root}: {line}")

    # 대표 번호 자체 대신 모든 쌍의 소속 관계를 대조한다.
    for a in range(size):
        for b in range(size):
            assert (labels[a] == labels[b]) == (
                b in reference.groups[a]
            )
    print("내장 집합 결과 일치: True")

    print("직접 구현 측정")
    print(
        f"합치기 시도={fast.union_calls}, "
        f"성공={fast.merges}, 찾기={fast.find_calls}"
    )
    print(
        f"압축 사용: 부모 이동={fast.parent_steps}, "
        f"부모 변경={fast.parent_writes}"
    )
    print(
        f"압축 제외: 부모 이동={plain.parent_steps}, "
        f"부모 변경={plain.parent_writes}"
    )
    print(
        f"내장 비교: 소속 검사={reference.membership_checks}, "
        f"멤버 이동={reference.member_moves}"
    )


def run_kruskal():
    # [7] 비용 오름차순으로 준비한 간선 배열이다.
    edges = (
        (0, 1, 1), (1, 2, 2), (0, 2, 3),
        (2, 3, 4), (0, 3, 5),
    )
    uf = UnionFind(4)
    cost = 0
    selected = 0
    rejected = 0
    for a, b, weight in edges:
        if uf.union(a, b):
            cost += weight
            selected += 1
            if selected == 3:
                break
        else:
            rejected += 1
    assert selected == 3
    print(
        f"크루스칼: 비용={cost}, 선택={selected}, "
        f"순환 제외={rejected}"
    )


def main():
    run_friends()
    run_kruskal()


if __name__ == "__main__":
    main()

줄별 해설

[1] 배열 초기화와 측정 범위를 정한다

parent와 rank는 원소 수만큼 한 번에 만든다. 정수 0은 바뀌지 않는 값이므로 [0] * size로 초기화해도 원소끼리 변경이 전파되지 않는다. 이후 반복문에서 각 부모를 자신의 번호로 설정한다. 이 과정의 시간과 두 배열의 공간은 모두 O(n)이다.

components는 현재 그룹 수다. 나머지 정수 필드는 측정용이다. 초기 배열을 채우는 저장은 parent_writes에 포함하지 않는다. 이 값은 초기화가 끝난 뒤 합치기와 압축이 수행한 부모 변경만 센다. _check는 파이썬에서 음수 인덱스가 뒤쪽 원소를 가리키는 동작을 막는다. 잘못된 번호가 조용히 다른 사람으로 해석되는 것을 방지한다.

[2] 첫 순회와 두 번째 순회를 나눈다

root는 처음에 출발 번호다. 부모가 자신과 다를 동안 한 단계씩 이동하며 parent_steps를 증가시킨다. 반복문이 끝나면 root가 대표다. 원래 입력 x는 그대로 남아 있으므로 압축 순회를 다시 시작할 수 있다.

next_node는 부모를 바꾸기 전의 다음 번호다. 이를 저장한 뒤 현재 부모가 대표와 다를 때만 배열을 수정한다. 이미 대표를 직접 가리키는 원소에는 같은 값을 다시 쓰지 않는다. 그 덕분에 parent_writes는 실제 값이 바뀐 횟수가 된다. 압축 여부를 False로 설정하면 첫 순회 결과만 반환한다.

한 번의 찾기에서 첫 순회가 k번 이동했다면 두 번째 순회도 k개의 연결을 확인한다. 압축 구현의 실제 작업량은 대략 두 순회와 고정 작업의 합이다. 이동 횟수만 보고 두 구현의 실행 시간을 곧바로 비교하면 안 된다. 압축의 목적은 이후 찾기의 경로를 줄이는 데 있다.

[3] 중복 합치기를 먼저 거른다

ra와 rb가 같으면 배열이나 그룹 수를 바꾸지 않고 False를 반환한다. 이 경우에도 대표를 알아내기 위한 찾기 두 번은 수행했다. 따라서 합치기 시도 수와 성공 수를 따로 센다.

첫 대표의 랭크가 더 작으면 두 대표 번호를 맞바꾼다. 이후에는 rb를 ra 밑에 붙이는 한 문장으로 방향을 통일할 수 있다. 같았던 랭크를 올리는 작업은 부모 연결 이후에 수행하지만 랭크 배열 자체는 아직 바뀌지 않았으므로 비교 결과는 유지된다. 그룹 수를 줄이는 위치도 성공 경로에만 있다.

[4] 내장 집합 비교의 비용 단위를 구분한다

비교 구현은 각 사람 번호를 딕셔너리의 키로 사용하고, 값으로 같은 그룹의 집합 객체를 저장한다. 객체는 메모리에 만들어진 하나의 값 덩어리다. 같은 그룹의 여러 키가 같은 집합을 가리키므로 한 곳에서 집합을 늘리면 해당 그룹의 다른 사람도 늘어난 집합을 보게 된다.

합칠 때는 오른쪽 집합의 모든 멤버를 왼쪽 집합에 넣고, 그 멤버의 딕셔너리 값도 왼쪽 집합으로 바꾼다. 서로 다른 그룹의 집합은 겹치지 않으므로 순회 중인 right 자체를 수정하지 않는다. 이미 같은 그룹이면 반복문 전에 반환한다.

파이썬 표준 라이브러리에 유니온 파인드가 기본 자료형으로 제공되는 것은 아니다. 이 코드는 내장 자료구조를 이용해 같은 요구를 구현한 비교 대상이다. 내부 해시 처리 횟수를 측정하지 않으며, 소속 검사 요청 수와 옮긴 멤버 수만 센다. 부모 이동 한 번과 멤버 이동 한 번은 서로 다른 작업이다.

[5]부터 [7]까지 결과와 응용을 확인한다

압축 구현, 압축을 끈 구현, 내장 비교 구현에 같은 관계를 같은 순서로 넣는다. assert는 조건이 거짓이면 실행을 중단하는 검증문이다. 질의의 답뿐 아니라 합치기의 성공 여부도 비교한다. 따라서 반복 등록을 새 합치기로 잘못 처리하면 실행 중 확인할 수 있다.

labels 배열에는 각 사람의 대표를 한 번씩 저장한다. 이후 출력은 이 배열만 읽으므로 측정 횟수를 더 늘리지 않는다. 그룹 출력의 이중 반복문은 O(n²)이다. 사람이 적은 예제를 단순하게 보여 주기 위한 출력 방식이며, 유니온 파인드 자체의 비용과 구분한다. 문자열을 이어 붙이는 출력 준비 비용도 그룹 연산 측정에는 들어가지 않는다.

내장 구현과 대조할 때는 대표 번호를 비교하지 않는다. 모든 사람 쌍에 대해 같은 그룹인지 확인한다. 이 검증은 O(n²)개의 쌍을 확인하지만 측정용 메서드를 호출하지 않는다. 내장 집합의 순회 순서가 달라져도 출력은 번호순으로 만들어지므로 결과는 결정적이다.

크루스칼 예제는 새 객체를 사용하므로 친구 그룹의 측정값에 영향을 주지 않는다. 네 정점의 트리는 간선 세 개를 선택하면 완성되므로 바로 멈춘다. 실제 선택 목록이 필요하다면 간선 수만큼 고정 배열을 미리 만들고 선택할 때마다 다음 칸에 저장하도록 확장할 수 있다.

실행 결과

macOS 또는 Linux에서 Python 3.12 이상으로 실행한다. 다음 명령은 프로그램을 실행하고 바로 끝난다.

python3 main.py

예상 출력은 다음과 같다.

친구 그룹 확인
가람 / 라온: 같다
가람 / 아람: 다르다
마루 / 아람: 같다
그룹 수: 2
그룹 0: 가람, 나래, 다온, 라온
그룹 4: 마루, 바다, 새봄, 아람
내장 집합 결과 일치: True
직접 구현 측정
합치기 시도=8, 성공=6, 찾기=30
압축 사용: 부모 이동=15, 부모 변경=8
압축 제외: 부모 이동=19, 부모 변경=6
내장 비교: 소속 검사=11, 멤버 이동=8
크루스칼: 비용=7, 선택=3, 순환 제외=1

찾기 30번은 합치기 여덟 번에서 16번, 질의 세 번에서 6번, 출력용 대표 수집에서 8번 발생한다. 압축을 사용한 부모 변경 8번은 성공한 합치기 6번과 추가 압축 2번이다. 두 번째 중복 관계를 처리할 무렵 3과 7의 부모가 각각 대표로 바로 바뀐다.

압축을 끄면 두 원소의 깊이가 그대로 남아 이후 질의와 대표 수집에서도 중간 부모를 거친다. 그 결과 이 입력에서는 부모 이동이 19번에서 15번으로 줄어든다. 작은 입력 한 번으로 O(m α(n))을 증명할 수는 없다. 이 측정은 압축이 추가 쓰기를 수행하고 이후 이동을 줄인다는 동작을 확인한다.

연산의 복잡도와 이번 코드에서 확인하는 작업

연산	시간 비용	관찰 지표	해석
초기화	O(n)	n개 부모 초기화	각 원소를 한 번 설정한다.
랭크만 사용한 찾기	최악 O(log n)	부모 이동	높이에 비례한다.
압축과 랭크를 쓴 찾기·합치기	분할 상환 O(α(n))	이동과 변경	여러 연산을 묶어 분석한다.
내장 비교의 합치기	평균 O(k)	오른쪽 멤버 k명 이동	해시 연산의 평균 비용을 가정한다.

내장 비교에서 소속 검사 11번은 합치기 여덟 번과 질의 세 번의 합이다. 옮긴 멤버는 차례로 1, 1, 2, 1, 1, 2명이며 중복 합치기는 아무도 옮기지 않는다. 합계는 8명이다. 이 숫자와 부모 이동 15번을 나란히 놓고 어느 구현이 더 빠르다고 결론 내릴 수는 없다. 작업 단위가 다르고, 내장 연산 내부의 비용도 제외했기 때문이다.

실무에서 자주 틀리는 것

대표를 찾지 않고 입력 번호를 연결한다

다음 코드는 a가 대표가 아닐 때 일부 가지의 소속만 바꿀 수 있다. 그룹 전체를 합치는 규칙을 깨뜨린다.

# 틀린 코드
self.parent[a] = b

대표를 먼저 구하고 대표끼리 연결한다. 아래는 연결 원칙만 나타낸 조각이며, 완성 코드에서는 랭크 비교도 함께 적용한다.

# 고친 코드
ra = self.find(a)
rb = self.find(b)
if ra != rb:
    self.parent[rb] = ra

이미 같은 그룹인데 그룹 수를 줄인다

관계 등록 수와 실제 합치기 수는 다르다. 같은 그룹의 관계가 다시 들어왔다고 그룹이 하나 더 사라지지 않는다.

# 틀린 코드
self.components -= 1
if ra == rb:
    return False

대표가 다른 경우에만 그룹 수를 줄인다. 같은 사람을 자기 자신과 합칠 때도 이 규칙으로 처리된다.

# 고친 코드
if ra == rb:
    return False
self.parent[rb] = ra
self.components -= 1

압축하면서 다음 이동 위치를 잃는다

부모를 덮어쓴 다음 그 부모로 이동하면 곧바로 대표에 도착한다. 출발점만 압축되고 원래 경로의 중간 원소를 건너뛴다. 그룹의 정답은 유지될 수 있지만 모든 방문 원소를 압축하려던 의도와 달라진다.

# 틀린 코드
while self.parent[current] != current:
    self.parent[current] = root
    current = self.parent[current]

이동할 번호를 먼저 저장한다. 계측을 포함할 때는 완성 코드처럼 값이 실제로 바뀌는지도 확인한다.

# 고친 코드
while self.parent[current] != current:
    next_node = self.parent[current]
    self.parent[current] = root
    current = next_node

부모 하나를 되돌려 관계 삭제를 구현한다

부모 연결은 원래 친구 관계가 아니다. 이미 압축까지 했다면 어느 관계 때문에 같은 그룹이 되었는지도 남아 있지 않다. 다음 코드는 친구 관계 하나를 지우는 동작이 아니다.

# 틀린 코드
uf.parent[a] = a

삭제가 드물고 데이터가 작다면 남아 있는 관계로 구조를 새로 만드는 방법을 사용할 수 있다. remaining_edges는 삭제 대상 관계를 제외해 준비한 입력이다.

# 고친 코드
uf = UnionFind(size)
for a, b in remaining_edges:
    uf.union(a, b)

이 방법에는 재구축 비용이 든다. 삭제와 질의가 빈번하다면 현재 구현과 다른 요구사항이므로 별도의 설계를 검토해야 한다.

한눈에 보기

요구사항과 유니온 파인드의 대응 관계

알고 싶은 것	사용할 정보	주의할 점
어느 그룹인가	find가 반환한 대표	대표는 업무상 그룹 이름이 아니다.
같은 그룹인가	두 대표의 일치 여부	직접 친구라는 뜻은 아니다.
그룹이 몇 개인가	components	성공한 합치기만 1을 뺀다.
찾기를 줄이려면	경로 압축	질의도 부모 배열을 바꿀 수 있다.
높이를 제한하려면	대표의 랭크	압축 후 실제 높이와 다를 수 있다.
간선을 선택해도 되는가	union의 반환값	크루스칼은 비용순 처리가 필요하다.

부모 배열과 랭크 배열의 공간은 O(n)이다. 연결 여부만 필요할 때 모든 간선을 저장하지 않아도 된다는 점이 유용하다. 다음 장에서는 이런 식으로 필요한 질문, 입력 변화, 허용할 비용을 기준으로 자료구조를 고르는 판단을 이어 간다.

연습 문제

1. 친구 그룹 예제의 마지막 두 중복 관계를 입력에서 제외하라. 질의와 대표 수집은 그대로 둘 때 찾기 호출 수, 부모 이동 수, 부모 변경 수를 압축 사용 여부별로 구하라.
2. 각 그룹의 인원수를 반환하는 group_size 메서드를 추가하라. 랭크를 인원수로 사용하지 말고 별도의 고정 크기 배열을 만들어라.
3. 크루스칼 예제에서 정점 수를 5로 바꾸고 정점 4에 연결되는 간선을 추가하지 않았다고 하자. 트리가 완성되지 않았음을 출력하도록 종료 조건과 검증을 수정하라.
4. 친구 그룹을 모두 합친 뒤 같은 질의 (0, 3)를 다섯 번 추가하라. 압축 구현과 압축 제외 구현의 부모 이동 증가량을 예상하고 확인하라.

정답과 해설

1. 합치기가 여섯 번이므로 찾기는 12 + 6 + 8 = 26번이다. 압축 사용 시 부모 이동은 11번, 부모 변경은 8번이다. 압축 제외 시 부모 이동은 13번, 부모 변경은 6번이다.

   압축 사용에서는 첫 질의 (0, 3)가 두 번 이동하며 3을 압축한다. 다음 질의 (0, 7)도 두 번 이동하며 7을 압축한다. 세 번째 질의는 한 번 이동한다. 대표 수집은 여섯 번 이동하므로 합계가 11이다. 압축 제외에서는 질의가 다섯 번, 대표 수집이 여덟 번 이동한다. relations의 끝 두 항목을 지우고 실행하면 측정값을 확인할 수 있다.

2. 생성자에 각 원소의 초기 인원수 1을 저장한다. 합치기가 성공할 때 최종 대표 ra에 rb의 인원수를 더한다. rb의 옛 인원수는 더 이상 읽지 않으므로 그대로 두어도 된다.

   # __init__에 추가
   self.sizes = [1] * size
   
   # union에서 최종 ra, rb를 정한 뒤 성공 경로에 추가
   self.sizes[ra] += self.sizes[rb]
   
   # UnionFind의 메서드로 추가
   def group_size(self, x):
       return self.sizes[self.find(x)]
   

   run_friends에서 관계 입력을 마친 뒤 assert fast.group_size(0) == 4로 확인할 수 있다. 이 메서드도 find를 호출하므로 원래 예제의 찾기 횟수와 이동 횟수는 늘어난다. 기존 출력과 비교하려면 별도 객체로 검사하거나 측정값이 달라지는 이유를 함께 기록한다.

3. 정점 수를 변수로 두고 목표 간선 수를 size − 1로 계산한다. 간선을 모두 처리한 뒤 선택 수가 목표보다 작으면 연결 실패를 출력한다. 기존 assert selected == 3도 이 판정으로 바꾼다.

   size = 5
   uf = UnionFind(size)
   target = size - 1
   # 기존 반복문의 중단 조건을 다음으로 바꾼다.
   # if selected == target:
   #     break
   
   # 반복문 뒤의 기존 assert 대신 사용한다.
   if selected != target:
       print(f"전체 연결 불가: 연결 요소={uf.components}")
   

   정점 0부터 3까지만 이어지므로 선택한 간선은 세 개이고 연결 요소는 두 개다. 출력은 전체 연결 불가: 연결 요소=2가 된다. 이때 선택한 간선들은 각 연결 요소 안에서 비용이 최소인 나무들을 이룬다.

4. 원래 예제의 대표 수집까지 끝난 상태를 기준으로 한다. 압축 구현에서는 3이 0을 바로 가리켜 질의 한 번에 부모 이동이 한 번 증가한다. 압축 제외 구현에서는 3 → 2 → 0을 따라가므로 두 번 증가한다. 다섯 번 반복하면 각각 5번과 10번 증가한다.

   before_fast = fast.parent_steps
   before_plain = plain.parent_steps
   for repeat in range(5):
       assert fast.same(0, 3)
       assert plain.same(0, 3)
   assert fast.parent_steps - before_fast == 5
   assert plain.parent_steps - before_plain == 10
   

   이 코드는 run_friends의 끝에 넣어 확인할 수 있다. 반복 질의의 답은 같지만 부모를 따라가는 작업량은 다르다. 결과의 정확성과 내부 작업량을 함께 관찰하면 최적화가 어떤 비용을 줄였는지 구체적으로 설명할 수 있다.