"친구의 친구는 친구다" — 유니온 파인드가 빛나는 순간

"이거 그래프 문제인데 BFS로는 시간 초과 나요" — 스터디에서 제일 자주 듣는 질문 중 하나다. 네트워크 연결, 집합 분류, 사이클 판별. 이런 키워드가 보이면 BFS/DFS보다 먼저 꺼내야 할 자료구조가 있다.

#유니온 파인드, 대체 언제 쓰는 건데

유니온 파인드(Union-Find), 또는 서로소 집합(Disjoint Set Union)은 이름 그대로 "합치고 찾는" 자료구조다. 핵심 연산은 딱 두 개:

• Find: 이 원소가 속한 그룹의 대표(루트)를 찾는다

• Union: 두 그룹을 하나로 합친다

이게 전부인데, 이 단순함이 오히려 문제를 풀 때 떠올리기 어려운 이유다. "아 이게 유니온 파인드구나" 하는 감을 잡으려면, 문제에서 어떤 시그널이 나오는지 알아야 한다.

시그널 정리:

• "같은 그룹인지 판별하라"

• "네트워크/섬을 연결하라"

• "사이클이 존재하는지 확인하라"

• "집합의 개수를 구하라"

카카오, 네이버, 삼성 — 어디서든 나온다. 프로그래머스 '네트워크', 백준 '집합의 표현(1717)', '여행 가자(1976)' 같은 문제가 대표적이다.

#기본 구현은 5줄이면 된다

parent = list(range(n))

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

def union(a, b):
    a, b = find(a), find(b)
    if a != b:
        parent[b] = a

진짜 이게 끝이다. 하지만 이 몇 줄 안에 성능을 좌우하는 핵심이 숨어 있다.

find 함수의 parent[x] = find(parent[x]) — 이게 **경로 압축(Path Compression)**이다. 한 번 루트를 찾으면 경로상 모든 노드를 루트에 직접 연결해버린다. 이걸 빼면 최악의 경우 O(n)이고, 넣으면 사실상 O(α(n)), 거의 상수 시간이다. α는 아커만 함수의 역함수인데 현실적인 입력 범위에서 4를 넘지 않으니까 O(1)이라고 생각해도 무방하다.

#union by rank, 꼭 해야 하나?

솔직히 코테 수준에서는 경로 압축만으로도 거의 다 통과한다. union by rank(또는 union by size)까지 붙이면 이론적으로 더 빠르지만, 시험장에서 빼먹었다고 시간 초과 나는 경우는 드물다.

그래도 알아둬야 하는 이유? 면접에서 "최적화 더 할 수 있냐"는 질문이 나올 때 대답할 수 있어야 하니까.

rank = [0] * n

def union(a, b):
    a, b = find(a), find(b)
    if a == b:
        return False  # 이미 같은 집합 → 사이클!
    if rank[a] < rank[b]:
        a, b = b, a
    parent[b] = a
    if rank[a] == rank[b]:
        rank[a] += 1
    return True

return False에 주목하자. 두 노드가 이미 같은 집합에 있는데 또 연결하려 한다 — 이건 사이클이 생겼다는 뜻이다. 크루스칼 알고리즘으로 최소 신장 트리를 구할 때도 이 로직을 그대로 가져다 쓴다. 간선을 가중치 순으로 정렬하고, union이 True를 리턴할 때만 MST에 추가하면 끝.

#실전 변형 3가지

1. 집합 개수 세기

초기 카운터를 n으로 놓고 union이 성공할 때마다 1을 뺀다. 마지막에 남은 값이 그룹 수. 프로그래머스 '네트워크' 문제가 정확히 이 패턴이다.

2. 가중치 유니온 파인드

백준 3780번처럼 간선에 비용이 붙는 경우. find로 경로 압축할 때 가중치도 같이 누적해야 한다. 난이도가 확 올라가는데, 대기업 코테에선 잘 안 나온다. 알고리즘 대회 지망이 아니라면 "이런 게 있다" 정도만 알면 충분하다.

3. 오프라인 쿼리 — 역순의 마법

"간선을 하나씩 제거할 때 컴포넌트 수 변화를 구하라" 타입. 제거를 직접 처리하면 자료구조가 복잡해진다. 발상을 뒤집자. 쿼리를 역순으로 뒤집으면 "제거"가 "추가"로 바뀌고, 그냥 유니온 파인드를 돌리면 된다. 이 역발상이 골드~플래티넘 문제에서 자주 등장하는데, 한 번 체화하면 여러 문제에 응용할 수 있다.

#BFS랑 어떻게 구분하냐

같은 "연결 요소"를 다루는 문제라도 도구 선택은 갈린다.

핵심은 간단하다. "연결됐냐 안 됐냐"만 중요하면 유니온 파인드, "어떻게 연결됐냐"(경로, 거리)가 중요하면 BFS/DFS. 이 기준 하나로 거의 다 걸러진다.

이번 주에 하나만 풀어보고 싶다면 백준 1717번 '집합의 표현'이 정석이다. find와 union만 구현하면 바로 AC. 거기서 감이 오면 1976번 '여행 가자', 4195번 '친구 네트워크'로 넘어가자. 유니온 파인드는 한 번 손에 익히면 그래프 문제에서 체감 난이도가 확 내려가는 몇 안 되는 자료구조다.