Union-Find란?
공통 원소가 없는 부분 집합들로 이루어진 트리 자료구조를 이용하여 union과 find를 사용하는 개념이라고 생각하면 된다.
이름에서 처럼 Union(합치기), Find(찾기) 연산에 유리한 점을 갖고있다.
처음에 아래와 같이 1~8 숫자가 각각 있는 상황이라면, 공통 원소가 없는 [1], [2]...[8] 부분 집합들(트리에서 각 노드)이라고 생각할 수 있다.
이후 아래와 같이 집합(트리)이 구성되는 상황이 있을 수 있다
이 때에도, union과 find를 잘 구현해놓으면 쉽게 루트 노드를 찾을 수 있고, 각 부분 집합들을 잘 합칠 수 있다.
구현은 아래 예시 코드로 보자.
구현 순서
- 각 부분집합들(각 노드)의 값(value)를 1이나 0, -1 등으로 초기화를 한다.(여기서는 -1)
즉, 각 노드의 값이 초기화 값이라면 그 노드는 루트(root) 노드이다. - union(a, b)을 구현한다. 합쳐야하는 상황에서 union(a, b)을 이용해 합치도록(a를 b의 루트 노드로 만들기) 한다.
- find(x)를 구현한다. 여기서 find(x) 함수는 x노드의 루트 노드를 찾아낸다.
문제 : 백준 1717 집합의 표현
<풀이 코드>
import sys
sys.setrecursionlimit(10**9)
n, m = map(int,sys.stdin.readline().rstrip().split())
# 1. 초기화
parent = [-1 for _ in range(n+1)]
# 2. union기능
def union(a,b) :
a = find(a)
b = find(b)
if a != b :
parent[a] = b
# 3. find 기능
def find(x) :
if parent[x] < 0:
return x
else :
parent[x] = find(parent[x])
return parent[x]
for _ in range(m) :
cmd, a, b = map(int,sys.stdin.readline().rstrip().split())
if cmd == 0:
union(a,b)
else:
if find(a) == find(b) :
print("YES")
else :
print("NO")참고하기 좋은 곳 :
고재개발