[Algorithm] 유니온 파인드(Union Find)와 서로소 집합(Disjoint Set)
집합을 표현할 때 사용하는 유니온 파인드(Union Find)와 서로소 집합(Disjoint Set)에 대해서 알아보자
환경 및 선수조건
- C++
유니온 파인드(Union Find)란?
정의
- 유니온 파인드(Union Find): 서로소 집합(Disjoint Set) 그리고 병합 찾기 집합(Merge Find Set)이라고도 불리며 여러 서로소 집합의 정보를 저장하고 있는 자료구조를 의미합니다.
예시
- 다음 아래와 같이 원소들이 있다고 가정을 했을 때
- 각각의 원소들이 어떤 원소들과 연결이 되어있는지 입력을 받는다고 가정하면(1-2, 2-5, 5-6, 5-8, 3-4 이런 방식으로) 아래와 같이 3개의 서로소 집합이 나올 수 있다.
구현
원리
- 배열을 이용해서 Tree 자료구조를 만들어 구현하며 위에 나와 있는
{1, 2, 5, 6, 8}, {3, 4}, {7}의 경우에는 아래처럼 표현 및 구현이 가능합니다. - 즉, 최상단 노드인 Root노드를 집합을 구분하는 ID처럼 생각하면 이해가 더 편합니다.
- 주어진 두 원소 또는 집합을 합하는
Union부분과 원소가 어떤 집합에 있는지 찾는Find함수로 이루어져있다. parent[i]: 원소i의 부모 노드를 가지고 있는 배열,parent[i]는i의 부모 노드
초기화
- 처음에 각각의 원소들은 연결된 정보가 없기 때문에 부모로 자기 자신을 가지고 있다.
- 즉, parent[i] = i;
for(int i=1; i<=n; i++){
parent[i] = i;
}
Find 함수
Find(x)함수: x로 들어온 원소의 Root노드를 반환
int Find(int x){
// Root인 경우 x를 반환
if(x == parent[x]){
return x;
}
else{
// 아니면 Root를 찾아감
int p = Find(parent[x]);
parent[x] = p;
return p;
}
}
Union 함수
Union(x,y)함수: x원소와 y원소를 합치는 함수로 y의 Root노드를 x로 한다.
// x와 y의 원소가 들어오면
// 각각 x에는 들어온 x의 Root 노드 y에는 들어온 y의 Root 노드를 저장해서 비교하고
// x에 y를 붙이는 방식 -> y의 Root 노드를 x로 설정
void Union(int x, int y){
x = Find(x);
y = Find(y);
if(x!=y){
parent[y] = x;
}
}
관련 문제 및 예제
#include <iostream>
#include <stdio.h>
using namespace std;
int parent[1000001];
int Find(int x){
if(x == parent[x]){
return x;
}
else{
int y = Find(parent[x]);
parent[x] = y;
return y;
}
}
void Union(int x, int y){
x = Find(x);
y = Find(y);
parent[y] = x;
}
int main(){
int n,m;
scanf("%d %d", &n, &m);
// 배열 생성 및 초기화
// 처음에는 자기 자신이 부모이다 -> 모두 떨어져있기 때문
for(int i=0; i<=n; i++){
parent[i] = i;
}
int op, a, b;
while(m--){
scanf("%d %d %d", &op, &a, &b);
if(op == 0){
Union(a,b);
}
else if(op == 1){
int a_parent = Find(a);
int b_parent = Find(b);
if(a_parent == b_parent){
printf("YES\n");
}
else{
printf("NO\n");
}
}
}
return 0;
}
#include <stdio.h>
#include <iostream>
using namespace std;
int computers;
int connections;
int parent[101];
int Find(int x){
if(x == parent[x]){
return x;
}
else{
int y = Find(parent[x]);
parent[x] = y;
return y;
}
}
void Union(int x, int y){
x = Find(x);
y = Find(y);
if(x!=y){
parent[y] = x;
}
}
int main() {
scanf("%d", &computers);
scanf("%d", &connections);
// 초기화
// 처음에는 각각 노드가 부모노드가 자기자신
for(int i=0; i<=computers; i++){
parent[i] = i;
}
int u,v;
while(connections--){
scanf("%d %d", &u, &v);
Union(u,v);
}
// Root 노드가 1인 노드를 검색해서 cnt에 더해줌
int cnt = 0;
for(int i=2; i<=computers; i++){
if(Find(1) == Find(i)) cnt++;
}
printf("%d\n", cnt);
return 0;
}