유니온 파인드는 연결 여부를 빠르게 확인하는 데 특화된 자료구조입니다. 그래프 문제에서 간선을 하나씩 보면서 두 점이 이미 같은 그룹인지 확인해야 할 때 특히 강합니다.
이 글에서는 서로소 집합이 무엇인지, 대표 원소로 연결성을 어떻게 판단하는지, 그리고 path compression과 union by rank 또는 union by size가 왜 속도를 끌어올리는지 한 흐름으로 정리합니다.
서로소 집합과 연결성
서로소 집합은 겹치지 않는 여러 그룹입니다. 각 원소는 정확히 하나의 그룹에만 속합니다.
유니온 파인드는 이 그룹들을 관리하면서 두 가지 질문에 답합니다.
- 두 원소가 같은 그룹에 속하는가
- 두 그룹을 하나로 합쳐도 되는가
그래프 문제로 바꾸면 더 직관적입니다. 정점은 원소이고, 간선으로 이어지면 같은 연결 요소가 될 수 있습니다. 지금까지 본 간선만 기준으로 두 정점이 이미 연결되었는지 묻는 순간 DSU가 잘 맞습니다.
핵심은 각 그룹의 대표 원소를 하나 정해 두고, 같은 대표를 가지면 같은 집합이라고 보는 것입니다.
기본 연산은 find와 union
- find(x): x가 속한 집합의 대표 원소를 찾습니다.
- union(a, b): a가 속한 집합과 b가 속한 집합을 합칩니다.
초기에는 모든 원소가 자기 자신만의 집합입니다.
parent = [0, 1, 2, 3, 4, 5]이 상태에서는 각 원소의 대표가 자기 자신입니다. 이후 union으로 그룹을 합치면 같은 집합의 원소들은 결국 같은 대표를 돌려주게 됩니다.
대표 원소로 연결 여부를 판단하는 이유
연결성 문제에서는 결국 같은 연결 요소인지가 중요합니다. DSU는 이 질문을 대표 비교로 바꿉니다.
- find(a)와 find(b)가 같으면 같은 집합입니다.
- find(a)와 find(b)가 다르면 아직 다른 집합입니다.
이렇게 바꾸면 그래프 전체를 다시 탐색하지 않아도 됩니다. BFS나 DFS를 매번 새로 돌리는 대신, 지금까지 합쳐진 결과만 parent 배열에 압축해서 들고 가는 셈입니다. 연결을 실제로 따라가는 방식이 궁금하다면 BFS와 DFS 차이 글도 같이 보셔도 좋습니다.
DSU의 핵심은 연결 자체를 매번 다시 찾지 않고, 이미 합쳐진 그룹의 대표만 비교한다는 점입니다.
단순 구현이 느려지는 이유
처음에는 parent 배열만으로도 DSU를 만들 수 있습니다. 문제는 합치는 순서가 나쁘면 트리가 한쪽으로 길게 늘어진다는 점입니다.
def find(x):
while parent[x] != x:
x = parent[x]
return x
def union(a, b):
ra = find(a)
rb = find(b)
if ra != rb:
parent[rb] = ra예를 들어 아래처럼 연결되면 마지막 원소는 대표를 찾기 위해 여러 칸을 타고 올라가야 합니다.
0 <- 1 <- 2 <- 3 <- 4 <- 5이런 구조에서는 find가 느립니다. 원소 수가 커질수록 비용이 커지고, 연결성 질의가 많으면 전체 성능이 급격히 나빠집니다.
path compression이 하는 일
path compression은 find 과정에서 방문한 노드들이 다음부터는 대표 원소를 더 직접 가리키게 만드는 최적화입니다.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]한 번 찾고 나면 길게 이어졌던 경로가 납작해져 이후 탐색이 훨씬 빨라집니다. 이 최적화의 포인트는 지금 한 번 찾는 비용을 내면서, 다음 탐색들을 더 싸게 만든다는 데 있습니다.
union by size와 rank가 필요한 이유
path compression만으로도 많이 빨라지지만, 애초에 트리가 너무 삐뚤어지지 않게 합치는 규칙도 중요합니다. 여기서 쓰는 전략이 union by size와 union by rank입니다.
union by size
원소 수가 작은 트리를 큰 트리 밑에 붙입니다. 그러면 전체 높이가 불필요하게 커지는 일을 줄일 수 있습니다.
def union(a, b):
ra = find(a)
rb = find(b)
if ra == rb:
return False
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
return Trueunion by rank
여기서 rank는 보통 트리 높이의 상한 비슷한 값으로 이해하면 됩니다. 낮은 rank 트리를 높은 rank 트리 밑에 붙이고, 두 rank가 같을 때만 한쪽 rank를 1 올립니다.
def union(a, b):
ra = find(a)
rb = find(b)
if ra == rb:
return False
if rank[ra] < rank[rb]:
ra, rb = rb, ra
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1
return True실전에서는 union by size와 union by rank 모두 충분히 자주 쓰입니다. 목적은 같습니다. 트리 높이를 작게 유지하는 것입니다.
path compression은 찾을 때 경로를 줄이고, union by size 또는 rank는 합칠 때 높이가 커지지 않게 막습니다.
왜 빠르다고 말할까
결론만 먼저 말하면, 두 최적화를 함께 쓰면 연산 하나하나가 거의 상수 시간처럼 느껴집니다.
엄밀히는 amortized complexity가 역 아커만 함수에 비례하는 수준입니다. 이름은 어렵지만, 실제 문제 크기에서는 매우 천천히 증가합니다. 중요한 점은 어떤 한 번의 연산이 항상 같은 비용이라는 뜻이 아니라, 많은 연산을 묶어서 보면 평균 비용이 매우 작다는 데 있습니다.
즉, DSU는 많이 쓸수록 경로가 정리되고 구조가 안정되기 때문에 더 강해지는 느낌의 자료구조라고 이해해도 좋습니다.
언제 DSU를 떠올릴까
다음 신호가 보이면 유니온 파인드를 의심해 볼 만합니다.
- 간선을 하나씩 추가한다
- 두 정점이 같은 그룹인지 자주 묻는다
- 사이클이 생기는지 확인해야 한다
- 여러 그룹을 합쳐 나간다
- 연결 요소 개수를 관리한다
- 크루스칼처럼 간선을 비용 순으로 보면서 합칠지 말지 결정한다
사이클 판별
무방향 그래프에서 간선 (a, b)를 볼 때, 이미 find(a)와 find(b)가 같다면 그 간선을 추가하는 순간 사이클이 생깁니다.
크루스칼 알고리즘
가중치가 낮은 간선부터 보면서, 서로 다른 집합일 때만 union을 합니다. 그러면 사이클을 피하면서 최소 신장 트리를 만들 수 있습니다. 가중치와 최단 경로 관점은 다익스트라와 BFS 비교 글를 같이 보면 그래프 문제 감각을 더 넓히는 데 도움이 됩니다.
파이썬 DSU 구현
아래 구현은 path compression과 union by size를 함께 넣은 형태입니다.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, a, b):
ra = self.find(a)
rb = self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
def connected(self, a, b):
return self.find(a) == self.find(b)짧지만 필요한 감각은 거의 다 들어 있습니다. parent는 누구 밑에 있는지 기억하고, size는 어느 트리가 더 큰지 판단하는 데 쓰이며, find는 대표를 찾으면서 경로를 압축합니다.
자주 헷갈리는 세 가지
대표 원소는 문제의 본질이 아닙니다
대표가 꼭 가장 작은 번호일 필요는 없습니다. 어떤 원소가 대표가 되느냐보다, 같은 집합이면 같은 대표가 나온다는 사실이 중요합니다.
rank는 항상 실제 높이와 같다고 보면 위험합니다
path compression이 들어가면 트리가 납작해지기 때문에 rank는 높이의 상한 정도로 이해하는 편이 안전합니다.
DSU는 간선 삭제가 많은 문제에는 잘 맞지 않습니다
DSU는 합치고 확인하는 방향에는 강하지만, 이미 합쳐진 관계를 자주 끊어야 하는 완전 동적 연결성 문제에는 그대로 쓰기 어렵습니다.
정리
유니온 파인드는 서로소 집합을 관리하는 자료구조입니다. 같은 집합인지 확인하는 질문을 대표 원소 비교로 바꾸기 때문에 연결성 문제를 빠르게 처리할 수 있습니다.
- path compression은 찾을 때 경로를 짧게 만듭니다.
- union by size 또는 union by rank는 합칠 때 트리 높이가 커지는 것을 막습니다.
- 문제에서 연결 여부, 그룹 병합, 사이클 판별, 크루스칼이 보이면 DSU를 떠올리면 됩니다.
더 자세한 참고 자료는 cp-algorithms의 DSU 문서와 Princeton Algorithms의 Union-Find 사례 연구를 확인해 보시면 좋습니다.
