유니온 파인드 솔루션

[1. 개요]

"상호 배타적 집합 == 유니온 파인드 == 분리집합" 

전부 같은 표현이며, 보통 "유니온 파인드" 라는 명칭이 고유 명사 처럼 사용된다고 한다.

 

유니온 파인드 자료구조 구현을 위해서는 세가지 연산이 필요하다.

초기화를 제외한 연산의 시간복잡도는 거의 상수시간이 되도록 작성해야 한다.

1. 초기화
   => 각 원소가 각각의 집합에 포함되도록 한다.
2. union
   => 두 원소를 하나의 집합을 합친다.
3. find
   => 원소가 속한 집합을 반환한다.

위 자료구조 구현 패턴을 정의하도록 한다.

초기화 구현 패턴

• int parents[]
  => 각 원소에 대해서 parents[i] = i 로 초기화 한다.
  => 자신의 부모가 자기 자신 => root
• int ranks[]
  => 각 원소가 속한 집합(트리)의 높이로, 자기자신만 속해 있으므로 최초는 전부 1로 초기화 한다.

find 구현 패턴 (재귀적으로 구현, 경로 압축 최적화 진행)

• 함수 프로토타입
  => find(u)
  => u 의 부모를 반환.
• 기저 사례
  => 자기 자신이 root 인 경우
• 재귀 호출
  => parents[u] = find(parents[u])

union 구현 패턴 (ranks 를 사용)

• 함수 프로토타입
  => union(u, v)
  => u 를 v 집합에 속하게 한다. (어디에 합친다는 기준이 중요하다.)
  => rank 가 작은쪽이 rank 가 높은쪽에 속하게 한다.
  => 높이가 더 높은 쪽에, 자식으로 들어간다면, 높이가 바뀌지 않기 때문이다.
• u 와 v 의 부모를 find() 를 통해 각각 구함,
• 두 부모가 같다면
  => 이미 같은 집합에 속함
  => 종료
• if ranks[pu] > ranks[pv] 
  => pu, pv 를 swap 한다.
• parents[pu] = pv
  => 실질적으로 u 와 v 를 합치는 연산
• if ranks[pu] == ranks[pv] 라면
  => 집합 크기가 둘다 1인 경우라 생각해보면,
  => v 가 속한 집합의 크기가 증가해야 한다.
  => ranks[pv] += 1;

활용 예시 (주로 그래프 관련 문제 해결을 위한 도구로 많이 사용됨.)

1. 그래프 연결성 확인
2. 그래프 사이클 확인
3. 두 노드를 연결하는 경로의 존재 확인
4. 집합 원소의 수 확인/추적
5. 구간에서 최대 값 갱신(?)
6. 각 그룹에 대표 값을 설정하여 문제 해결

---

[2. 예제]

• https://testkernelv2.tistory.com/484
• https://testkernelv2.tistory.com/569
• https://testkernelv2.tistory.com/570
• https://testkernelv2.tistory.com/571
• e