Find 연산
- 대표노드를 찾는 연산
- O(logN)의 시간복잡도를 갖는다
- 맨 처음에는 자기 자신으로 초기화 되어있다.
- 재귀적으로 구현할때 반드시 리턴값으로 업데이트 해줘서 경로 압축을 해줘야한다
Union 연산
- 두 집합을 합치는 연산
- 합칠때는 각각의 대표노드를 찾아서 한쪽의 대표노트로 값을 바꿔주면 된다(편의상 작은쪽으로)
- 선택된 노드끼리 연결하는게 아니라 대표노드끼리 연결해야함
활용 용도(발상법)
1. 네트워크 연결성 검사
네트워크 내의 노드들이 서로 연결되어 있는지, 또는 두 노드가 같은 네트워크 내에 있는지를 판별할 때
예를 들어, 컴퓨터 네트워크나 소셜 네트워크에서 두 사용자가 서로 연결되어 있는지 확인할때
2. 최소 신장 트리 알고리즘
최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 알고리즘인 크루스칼(Kruskal) 알고리즘에서 중요한 역할
크루스칼 알고리즘은 간선들을 가중치에 따라 오름차순으로 정렬한 후, 유니온 파인드를 사용하여 사이클이 형성되지 않게 하면서 간선들을 선택
3. 동적 연결성 문제
시간에 따라 변화하는 그래프에서 연결성을 관리하는 문제에서 유용.
예를 들어, 온라인 게임에서 플레이어 그룹의 형성과 해체, 또는 다양한 동적 시스템에서 구성 요소들의 연결 상태를 추적
4. 사이클 판별
그래프 내에서 사이클(cycle)이 존재하는지 여부를 판별할 때
특히 무방향 그래프에서, 두 노드를 연결하는 간선을 추가할 때 이미 같은 집합에 속해 있다면, 그 간선을 추가하면 사이클이 형성
5. 집합의 분할과 병합
여러 개의 집합을 관리하면서 빈번하게 같은 집합에 속해 있는지 묻거나
집합들 사이의 병합(union)과 분할(split)을 수행하는 알고리즘 문제
C++ 구현
#include <bits/stdc++.h>
using namespace std;
int r[1000005];
int find_f(int n){
if(r[n] == n)
return n;
else
// 중요: 재귀를 하면서 최종 결과가 경로들에 반영 되도록
// 경로 압축해주는 부분
return r[n] = find_f(r[n]);
}
void union_f(int a, int b){
int r_a = find_f(a);
int r_b = find_f(b);
// 대표노드가 같다면 같은 집합임으로 연결할 필요없음
if(r_a == r_b) return;
// 주의: 현재 노드끼리가 아니라 대표노드끼리 관계를 설정
// 즉 대표노드끼리 연결해줌
// 편의상 작은 대표노드가 되게
// 지금은 아니지만 나중에 find 연산시에 경로 압축이 될것임
if(r_a < r_b) r[r_b] = r_a;
else r[r_a] = r_b;
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin >> n >> m;
// 초기화
for(int i=0 ; i<=n; i++)
r[i] = i;
while(m--){
int q, a, b;
cin >> q >> a >> b;
if(q == 0)
union_f(a,b);
else{
string result = (find_f(a) == find_f(b))? "YES" : "NO";
cout << result << '\n';
}
}
}