🔎 유니온 파인드란?
유니온 파인드(Union-Find)는 여러 노드가 있을 때, 두 노드가 같은 집합(그래프)에 속해 있는지 판별하는 자료구조입니다. '서로소 집합(Disjoint Set)' 자료구조라고도 불리며, 이름에서 알 수 있듯이 다음과 같은 두 가지 핵심 연산으로 구성됩니다.
find: 특정 노드가 속한 집합의 대표 노드(루트)를 찾는 연산union: 두 노드가 속한 집합을 하나로 합치는 연산
이 자료구조는 주로 그래프 알고리즘에서 두 노드의 연결성을 확인하거나 사이클 발생 여부를 판별할 때 매우 유용하게 사용됩니다.
⚙️ 핵심 원리
유니온 파인드의 핵심은 각 노드가 어떤 집합에 속해 있는지를 부모 노드를 이용해 표현하는 것입니다.
- 처음에는 모든 노드가 자기 자신을 부모로 가리키는, 즉 각각이 별개의 집합을 이룹니다.
- 두 노드를 합치는
union연산이 수행되면, 한 노드의 부모를 다른 노드로 설정하여 두 집합을 연결합니다. - 이 과정을 반복하면, 같은 집합에 속한 노드들은 결국 동일한 대표 노드(루트)를 공유하게 됩니다.
🐍 Python으로 구현하기
1. 초기화
먼저, 각 노드의 부모를 저장할 리스트를 만듭니다. 처음에는 모든 노드가 연결되어 있지 않으므로, 각 노드의 대표 노드는 자기 자신입니다. parent 리스트를 자신의 인덱스 값으로 초기화합니다.
# N: 노드의 개수
parent = [i for i in range(N + 1)]2. find 연산: 대표 노드 찾기
find 연산은 특정 노드 a의 대표 노드를 찾는 함수입니다. 재귀 호출을 이용해 부모 노드를 계속 거슬러 올라가 루트를 찾습니다.
이때 경로 압축(Path Compression)이라는 최적화 기법을 적용하는 것이 중요합니다. 경로 압축은 find를 수행하는 과정에서 만나는 모든 노드가 최종적으로 찾은 대표 노드를 직접 가리키도록 만드는 기법입니다. 이를 통해 트리의 높이가 낮아져 시간 복잡도가 크게 개선됩니다.
def find(a):
# 자기 자신이 대표 노드이면 자신을 반환
if parent[a] == a:
return a
# 재귀를 통해 대표 노드를 찾고, 부모를 대표 노드로 갱신 (경로 압축)
parent[a] = find(parent[a])
return parent[a]3. union 연산: 두 집합 합치기
union 연산은 두 노드 a와 b가 속한 집합을 합칩니다.
find 연산을 통해 a와 b의 대표 노드를 각각 찾습니다.
두 대표 노드가 다르다면, 두 노드는 다른 집합에 속해 있다는 의미이므로 한쪽의 대표 노드를 다른 쪽의 부모로 만들어 두 집합을 합칩니다.
def union(a, b):
# 각 노드의 대표 노드를 찾음
a = find(a)
b = find(b)
# 대표 노드가 다를 경우, 하나의 집합으로 합침
if a != b:
parent[b] = a4. 두 노드의 연결 상태 확인
두 노드가 같은 집합에 속해 있는지 확인하려면, 두 노드의 대표 노드가 같은지만 비교하면 됩니다.
def check_same_set(a, b):
# 각 노드의 대표 노드를 찾음
a = find(a)
b = find(b)
# 대표 노드가 같으면 true, 다르면 false 반환
return a == b[백준] 1717번: 집합의 표현
import sys
# Python의 기본 재귀 깊이 제한은 1,000이므로,
# 노드의 개수가 많을 경우를 대비해 재귀 깊이를 10^6까지 늘림
sys.setrecursionlimit(10 ** 6)
# N: 노드의 개수, M: 질의(연산)의 개수
# sys.stdin.readline()을 사용하여 입력을 빠르게 처리
N, M = map(int, sys.stdin.readline().split())
# 각 노드의 부모 노드를 저장하는 리스트
# 처음에는 모든 노드가 자기 자신을 부모로 가리키도록 초기화
# 예: parent[3] = 3
parent = [i for i in range(N + 1)]
# --- 함수 정의 ---
# 특정 노드 a의 대표 노드(루트)를 찾는 함수
def find(a):
# 1. 기저 조건(Base Case): 만약 노드 a의 부모가 자기 자신이면, a는 루트 노드임
if parent[a] == a:
return a
# 2. 경로 압축(Path Compression): 재귀적으로 루트를 찾아 올라가면서
# 경로상의 모든 노드들의 부모를 최종 루트로 직접 연결함
# 이를 통해 트리의 높이를 낮춰 시간 복잡도를 최적화
parent[a] = find(parent[a])
return parent[a]
# 두 노드 a와 b가 속한 집합을 합치는 함수
def union(a, b):
# find 함수를 호출하여 각 노드의 대표 노드를 찾음
root_a = find(a)
root_b = find(b)
# 두 노드의 대표 노드가 다르다면, 아직 다른 집합에 속해 있다는 의미
if root_a != root_b:
# 한쪽의 대표 노드를 다른 쪽의 대표 노드의 자식으로 만들어 두 집합을 합침
# 여기서는 b의 대표 노드가 a의 대표 노드를 가리키도록 설정
parent[root_b] = root_a
# 두 노드 a와 b가 같은 집합에 속해 있는지 확인하는 함수
def check_same_set(a, b):
# 각 노드의 대표 노드를 찾음
root_a = find(a)
root_b = find(b)
# 두 노드의 대표 노드가 같다면, 같은 집합에 속해 있다는 의미
if root_a == root_b:
print("YES")
else:
print("NO")
# --- 메인 로직 ---
# M개의 질의(연산)를 처리하기 위해 반복
for _ in range(M):
# 연산의 종류(question)와 두 노드(a, b)를 입력받음
question, a, b = map(int, sys.stdin.readline().split())
# question이 0이면 union 연산을 수행
if question == 0:
union(a, b)
# question이 1이면 두 노드가 같은 집합인지 확인하는 연산을 수행
else:
check_same_set(a, b)