유니온 파인드 (Union Find)

= 분리 집합(Disjoint Set)

 

코딩테스트에 종종 등장하는 주제이다.

1. 유니온 파인드란?

그룹을 관리하기 위한 자료구조로, Union + Find 두 가지 기능을 가지고 있다. 

Union: 그룹간의 통합 (합치는) 연산

Find: 그 그룹의 대장(Boss) 원소를 찾는 연산

 

그래프를 그려서 이해하면 더 쉽다.

 

2. 유니온 파인드를 사용하는 경우

1. 특정 원소들이 같은 그룹에 속해있는지 확인해야 할 때

2. 그룹 간 통합 등의 동작이 필요할 때

 

3. 유니온 파인드의 특징

1. 각 그룹에는 대장(Boss)가 있다.

2. 그룹의 원소가 하나면 -> 단일 조직(단일 그룹)이다.

3. 그룹 간의 통합이 가능하다. 이 때, 한 그룹이 다른 그룹 내부로 들어가는 방식으로 통합이 된다. (흡수 통합)

통합시 흡수된 하위 그룹의 boss는 상위 그룹의 boss로 바뀐다. 

 

4. 유니온 파인드의 기능

# UNION : 통합

특정 그룹 밑으로 다른 그룹이 흡수되어 통합된다. 

 

# FIND : 보스 찾기

원소 하나가 주어지면, 그 원소가 속한 그룹의 boss를 찾을 수 있다. 

 

5. 구현 방법

- DAT(Direct Address Table: 키 값을 주소로 사용하는 테이블 = 해시 테이블)을 이용한다.

- DAT에 자신이 속한 그룹의 boss를 나타내는 방식, boss의 DAT는 비워놓는다.

-  Find의 원리 : 주어진 원소의 DAT를 참조하고, 그 인덱스로 계속 타고가서

   DAT가 비어있는 원소를 찾으면 그 원소가 그룹의 boss이다. 

 

6. 표현

union(a, b); //b가 a 아래로 들어간다(boss: a)
union(c, d);
union(d, b);

// union 결과로 만들어진 그룹의 최종 boss: c

 

7. C++ 유니온 파인드 구현 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

char vect[200]; // DAT 배열

// FIND
char getBoss(char ch) {
  if (vect[ch] == 0) return ch;
  char ret = getBoss(vect[ch]);
  // 경로압축
  vect[ch] = ret;
  return ret;
}

// UNION(a, b)
void setGroup(char a, char b) {
  // 문자 두개 입력받고, 각각의 boss를 구해서 boss가 다르면 합쳐줌
  char bossA = getBoss(a);
  char bossB = getBoss(b);
  if (bossA == bossB) return;
  vect[bossB] = bossA;
}

int main() {
  setGroup('A', 'B');
  setGroup('D', 'A');
  setGroup('E', 'D');
  setGroup('K', 'R');

  char a, b;
  cin >> a >> b;

  if (getBoss(a) == getBoss(b)) cout << '두 원소는 같은 그룹';
  else cout << '두 원소는 다른 그룹';

  return 0;
}

 

---

백준 단계별 [유니온 파인드]

https://www.acmicpc.net/step/14

유니온 파인드 단계

 

백준 알고리즘별 분류 [분리 집합]

https://www.acmicpc.net/problemset?sort=ac_desc&algo=81 

문제 - 1 페이지