[Algorithm] Union-Find

Union-Find(유니온 파인드)

그래프 알고리즘 중 하나로 서로소(disjoint sets) 집합 자료구조이다. 
서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 

서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현하는데, 서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.

1. union(합집합)연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
       - A와 B의 루트 노트 A', B'를 각각 찾는다.
       - A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다.)

2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.

17. Union-Find(합집합 찾기) : 네이버 블로그 (naver.com)

17. Union-Find(합집합 찾기)

출처: 취업을 위한 이것이 코딩 테스트다 with 파이썬