[알고리즘 코어 파헤치기] 유니온 파인드 & 크루스칼 완벽 해부 - 최소 비용으로 세계 통합하기

학습 철학 회고
그래프 알고리즘 중 최소 신장 트리(MST)를 구하는 크루스칼 알고리즘은 '그리디'와 '자료구조'의 완벽한 융합체입니다. 복잡한 2차원 간선 배열을 BFS로 힘들게 탐색하는 대신, 1차원 부모 배열을 활용한 '유니온 파인드(Union-Find)'의 우아한 추상화를 통해 순환(Cycle)을 완벽하게 통제하는 뼈대를 세웁니다.

📌 개념 요약: 유니온 파인드 (Disjoint Set)

수많은 노드들이 서로 연결되어 있는지(같은 네트워크/조직인지) 판별하기 위한 자료구조입니다.

• Find (보스 찾기): 특정 노드의 '최상위 부모(Root)'를 찾습니다.
• Union (조직 병합): 두 노드가 속한 각각의 그룹을 하나로 합칩니다. 한쪽 보스를 다른 쪽 보스의 부하로 만듭니다.

📌 개념 요약: 크루스칼 (Kruskal's Algorithm)

가장 적은 비용으로 모든 노드를 연결하는 최소 신장 트리(MST)를 구하는 알고리즘입니다.
1. 모든 간선(도로)을 비용 기준으로 오름차순 정렬합니다. (Greedy)
2. 가장 싼 간선부터 확인하며, 두 노드의 보스(Root)가 다를 때만 도로를 연결(Union)합니다.
3. 보스가 같다면 이미 연결된 그룹이므로 버립니다. (순환/Cycle 방지)

💻 추상화된 템플릿 코드 (유니온 파인드 & 크루스칼)

가장 빈번하게 실수하는 Union 연산의 부모 갱신 로직과, 탐색 시간을 $O(1)$에 가깝게 줄여주는 Find 연산의 경로 압축(Path Compression)이 완벽하게 반영된 순수 템플릿입니다.

# ----------------------------------------
# 1. 유니온 파인드 (Union-Find) 핵심 모듈
# ----------------------------------------

def find_parent(parent, x):
    # 자기 자신이 보스가 아니라면, 진짜 보스를 찾을 때까지 재귀적으로 파고듦
    if parent[x] != x:
        # [핵심 최적화: 경로 압축] 
        # 거쳐간 모든 노드의 부모를 최상위 보스로 바로 갱신해버림 (다음 탐색 시간 O(1) 단축)
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    # 1. 각 노드의 진짜 보스(Root)를 찾음
    root_a = find_parent(parent, a)
    root_b = find_parent(parent, b)
    
    # 2. 보스가 다르다면 병합 진행 (일반적으로 번호가 작은 쪽이 보스가 되도록 규칙 설정)
    if root_a < root_b:
        parent[root_b] = root_a
    else:
        parent[root_a] = root_b

# ----------------------------------------
# 2. 크루스칼 (Kruskal) 메인 템플릿
# ----------------------------------------

def kruskal_template(v, edges):
    """
    :param v: 노드의 개수
    :param edges: (비용, 노드A, 노드B) 형태의 간선 리스트
    """
    # 1. 부모 테이블 초기화: 처음엔 모두 자기 자신이 보스
    parent = [0] * (v + 1)
    for i in range(1, v + 1):
        parent[i] = i
        
    # 2. 간선을 비용 기준으로 오름차순 정렬 (Greedy 철학)
    edges.sort()
    
    total_cost = 0
    edge_count = 0 # 조기 종료를 위한 간선 개수 카운팅
    
    # 3. 가장 싼 간선부터 하나씩 확인
    for cost, a, b in edges:
        
        # [방어 로직] 사이클이 발생하지 않는 경우에만(보스가 다를 때만) 연결
        if find_parent(parent, a) != find_parent(parent, b):
            union_parent(parent, a, b) # 조직 병합
            total_cost += cost         # 비용 합산
            edge_count += 1
            
            # [최적화] 모든 노드가 연결되려면 간선은 정확히 v - 1개가 필요함
            if edge_count == v - 1:
                break
                
    return total_cost

🚨 설계 및 회고

• 치명적 실수 방어 (Union 로직): 초보자들이 union_parent를 짤 때 parent[b] = a라고 잘못 작성하여, 최상위 보스가 아닌 말단 부하의 부모만 바꿔버리는 치명적인 논리 오류를 범하곤 합니다. 반드시 find_parent를 통해 양쪽의 최상위 보스(root_a, root_b)를 먼저 찾은 뒤, 보스끼리 계급장을 떼고 연결(parent[root_b] = root_a)해야 합니다.
• 경로 압축 (Path Compression): find 함수에서 return find_parent(...)를 하지 않고 parent[x] = find_parent(...)로 값을 덮어씌우는 이 단 한 줄의 코드가, 일렬로 늘어선 최악의 트리 형태 $O(V)$를 $O(\log V)$ 수준의 평평한 트리로 마법처럼 압축해 줍니다.

🚨 아키텍처 개선: 중복 검사 제거와 union 함수의 최적화

크루스칼 알고리즘 템플릿을 분석하다 보면 메인 루프에서 다음과 같은 구조를 마주하게 됩니다.

# [방어 로직] 사이클이 발생하지 않는 경우에만(보스가 다를 때만) 연결
if find_parent(parent, a) != find_parent(parent, b):
    union_parent(parent, a, b) # 조직 병합
    total_cost += cost         # 비용 합산

이 코드는 논리적으로 완벽하지만, 메인 루프에서 부모를 굳이 한 번 더 확인해야 했던 이유는, 기존의 union_parent 함수가 병합의 성공 여부(사이클 발생 여부)를 외부로 반환(Return)하지 않고 침묵했기 때문입니다.

만약 메인 루프에서 if 조건문을 빼버리고 함수를 바로 호출한다면, 사이클을 만드는 무효한 간선의 비용까지 total_cost에 합산되는 치명적인 논리 오류가 발생합니다.

이러한 중복을 제거하고 응집도를 높이기 위해, union_parent 함수가 단방향 실행으로 끝나지 않고 성공 여부를 반환(Boolean Return)하도록 아키텍처를 수정할 수 있습니다.

1. union_parent 함수 개선

def union_parent(parent, a, b):
    root_a = find_parent(parent, a)
    root_b = find_parent(parent, b)
    
    # 이미 같은 보스라면 사이클 발생. 병합하지 않고 False 반환
    if root_a == root_b:
        return False
        
    # 보스가 다르다면 병합 후 True 반환
    if root_a < root_b:
        parent[root_b] = root_a
    else:
        parent[root_a] = root_b
        
    return True

2. 메인 루프 개선

for cost, a, b in edges:
    # union_parent가 True(새로운 병합 성공)를 반환했을 때만 내부 로직(비용 및 간선 추가) 실행
    if union_parent(parent, a, b):
        total_cost += cost
        edge_count += 1
        
        # [최적화] 모든 노드가 연결되려면 간선은 정확히 v - 1개가 필요함
        if edge_count == v - 1:
            break

이렇게 설계하면 메인 루프에서 불필요하게 find_parent를 반복 호출하는 일을 막아 시간 복잡도를 최적화하고, 코드의 가독성과 책임 분배를 명확히 할 수 있습니다.