[Algorithm] Union Find(유니온 파인드)

Union Find

• 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조
  • Disjoint-set(서로소 집합, 상호배타 집합) : 서로 중복 포함된 원소가 없는 집합들. 즉, 교집합이 없다.
    집합에 속한 대표자(representative)를 통해 각 집합을 구분한다.
• Make-Set, Find, Union의 세 연산을 이용한다.
• make-set(x)
  • 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
  • parents = [i for i in range(n)]과 같이 집합 생성
• find(x)
  • x를 포함하는 집합을 찾는 연산
  • 재귀 혹은 반복문을 통해 구현할 수 있다.

# 재귀
def find(x):
	if x == parents[x]:	# 자기 자신이 부모 노드라면(루트 노드) return x 
    	return x
    parents[x] = find(parents[x])	# 부모 노드 찾기 및 갱신
    return parents[x]
    
# while 문 사용
def find(x):
	while x != parents[x]:
    	x = parents[x]
    return x

• union(x, y)
  • x와 y를 포함하는 두 집합을 통합하는 연산

def union(x, y)::
	x = find(x)
    y = find(y)
    
    parents[y] = x

 

 

 

 

 

 

 

관련 문제(백준 1976) 풀이

https://eunjng.tistory.com/85

[BOJ] 1976 여행 가자 | Python