유니온 파인드 쉽게 이해하기의 핵심은 알고리즘 이름을 외우는 것이 아니라, parent 배열이 무엇을 저장하고 무엇을 줄여 주는지 감을 잡는 데 있습니다. find, union, path compression 같은 용어는 외웠는데도 문제에서 잘 못 쓰는 이유는 이 구조가 머릿속에서 그림처럼 안 잡히기 때문입니다.
이번 글에서는 유니온 파인드를 여러 원소가 같은 그룹인지 빠르게 확인하고, 두 그룹을 합치는 구조로 설명하겠습니다. 이름보다 동작 감각에 집중하겠습니다.
유니온 파인드는 어떤 문제를 위해 존재할까
이 자료구조는 “두 원소가 같은 그룹인가?”를 반복해서 확인해야 할 때 강합니다. 예를 들어 친구 관계, 네트워크 연결, 간선 추가, 사이클 판별, 최소 신장 트리 같은 문제에서 자주 등장합니다.
BFS나 DFS도 연결성을 볼 수 있지만, 간선을 하나씩 추가하면서 매번 빠르게 같은 집합인지 확인해야 하는 상황에서는 유니온 파인드가 훨씬 자연스럽습니다.
parent 배열은 무엇을 저장할까
parent 배열은 각 원소가 현재 어떤 대표를 따라가고 있는지를 저장합니다. 즉 각 원소가 자기 집합의 루트까지 연결된 길을 간접적으로 들고 있다고 생각하면 됩니다.
처음에는 보통 각 원소가 자기 자신을 대표로 가집니다. 그래서 parent[x] = x 입니다. 이후 union이 일어나면 한 집합의 루트가 다른 집합의 루트를 가리키게 됩니다.
결국 parent 배열은 “지금 이 원소가 어느 그룹 쪽으로 연결되어 있는가”를 압축해서 담고 있는 셈입니다.
find는 왜 대표를 찾는 함수일까
같은 그룹인지 확인하려면 각 원소가 결국 어떤 루트에 도달하는지를 보면 됩니다. 루트가 같으면 같은 그룹이고, 다르면 다른 그룹입니다. find는 바로 그 루트를 찾는 함수입니다.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]이 함수는 parent를 따라 위로 올라가다가 자기 자신을 부모로 가진 루트를 만나면 멈춥니다. 그리고 올라가는 중간 노드들의 parent를 바로 루트로 바꿔 줍니다. 이 한 줄이 path compression입니다.
disjoint-set 개념을 보면 집합을 서로 겹치지 않게 관리하고 빠르게 합치는 구조라는 점이 강조됩니다. 실전에서는 이 설명이 결국 parent 배열과 경로 압축 감각으로 이어집니다.
union은 정확히 무엇을 하는가
union은 두 원소가 속한 집합을 하나로 합칩니다. 중요한 것은 원소 자체를 막무가내로 연결하는 것이 아니라, 각 원소의 루트를 먼저 찾고 루트끼리 연결한다는 점입니다.
def union(a, b):
ra = find(a)
rb = find(b)
if ra != rb:
parent[rb] = ra즉 union의 핵심은 “두 그룹의 대표를 합친다”는 데 있습니다. 그래서 find와 union이 항상 같이 나옵니다.
path compression이 왜 그렇게 중요한가
parent를 따라 루트를 찾는 과정이 길어질수록 find는 느려집니다. 그런데 한 번 루트를 찾을 때 중간 노드들의 parent를 바로 루트로 바꿔 두면, 다음번 find는 훨씬 짧아집니다.
즉 path compression은 “이번 탐색만 빠르게 끝내는 기법”이 아니라, 이번 탐색을 하면서 미래 탐색까지 함께 싸게 만드는 기법입니다.
그래서 유니온 파인드는 반복 호출이 많을수록 성능 차이가 크게 느껴집니다.
작은 예시로 parent 배열 변화 보기
원소가 1, 2, 3, 4라고 해보겠습니다. 처음에는 각각 자기 자신이 루트입니다.
parent = [0, 1, 2, 3, 4]이제 union(1, 2)를 하면 2의 루트를 1 쪽으로 붙일 수 있습니다. 이어서 union(2, 3)을 하면 find(2)는 결국 1을 가리키므로 3도 1 쪽으로 묶이게 됩니다.
처음에는 3이 2를 거쳐 1로 가도록 남아 있을 수 있지만, find(3)을 한 번 하고 나면 path compression 덕분에 바로 1을 가리키게 바뀝니다. 이때부터 다음 find는 훨씬 짧아집니다.
문제에서 어떤 신호가 보이면 떠올려야 할까
- 두 원소가 같은 그룹인지 반복해서 물어본다
- 간선을 하나씩 추가하면서 연결 여부를 관리한다
- 사이클이 생기는지 확인해야 한다
- 최소 신장 트리처럼 집합 병합이 핵심이다
그래프 문제라고 해서 항상 BFS나 DFS부터 떠올릴 필요는 없습니다. 연결 확인과 집합 병합이 문제의 중심이면 유니온 파인드 쪽이 더 맞을 수 있습니다.
연결 관계를 빠르게 좁힌다는 감각은 이분 탐색 글처럼 구조를 효율적으로 줄여 가는 사고와도 닿아 있고, 자료구조 선택 기준은 힙 글과도 비교해 볼 수 있습니다.
입문자가 자주 하는 실수
- find 없이 union을 해서 루트가 아니라 중간 노드를 붙인다
- parent 배열이 실제 친구 목록이나 간선 목록을 저장한다고 오해한다
- path compression을 빼먹고도 왜 느린지 감을 못 잡는다
- 문제 신호가 연결 확인인데도 매번 BFS/DFS를 새로 돌리려 한다
특히 두 번째 실수가 많습니다. parent 배열은 모든 연결을 그대로 저장하는 표가 아니라, 대표를 따라가는 압축된 길입니다.
마무리
유니온 파인드를 이해하는 핵심은 parent 배열이 원소 간 연결 관계를 압축해서 관리하는 구조라는 점을 보는 데 있습니다.
즉 함수 이름을 외우기보다, 같은 집합인지 빠르게 확인하고 두 집합을 빠르게 합쳐야 하는 문제인가를 먼저 보는 감각이 중요합니다.
