서로소 집합
서로소 집합이란, 중복포함된 원소가 없는 집합이다. 서로소 집합은 교집합이 없고, 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다.
위그림에서 첫번째 A B는 서로소 관계가 아니고, 두번째 A B는 서로소 관계이다.
서로소 집합을 표현하는 방법에는 연결리스트로 표현하는 방법, 트리로 표현하는 방법 두가지가 있다.
서로소 집합 연산
서로소 집합 연산은 아래의 세 함수를 이용해서 진행된다.
Make-Set(x) : 집합생성(x원소로 갖는)
Find-Set(x) : x가 속한 집합 찾기(대표자 return하기)
Union(x,y) : x,y원소를 하나의 집합으로 만들기
- 서로소집합 x,y 만 union 해줘야됨(Findset 사용해서 보면됨)
- 대표자끼리 합친다.
- Make-Set
- 루트가 대표자
- 부모인덱스랑 자신의 인덱스가 다르면 같을때까지 올라가서 부모 찾기
- 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
Make-Set(x):
p[x]<-x- Find-Set
- x를 포함하는 집합을 찾는 연산
Find-Set(x):
If x==p[x] : Return x
Else : Return Find-Set(p[x])- Union
- x, y포함하는 두 집합을 통합하는 연산
Union(x):
If Find-Set(y) == Find-Set(x) Return;
P[Find-Set(y)]<-Find-Set(x) //대표자끼리 합치는것
Rank를 이용한 Union (효율 높이기)
- 각 노드는 자신을 루트로 하는 subtree높이를 rank로 저장한다.
- 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다.
path compression 를 더 빈번하게 쓴다. - 연산의 효율을 높이기 위해서 사용한다.
- Find-Set할때 모든 노드들이 root가리키도록 포인터를 바꿔준다.
- Find-Set(x): If x==p[x] : Return x Else : Return px[x]=Find-Set(p[x]) //대표자 알아와서 나의 부모로 바꾸기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static int n,m;
static int[] parents;
static void make() {
parents = new int[n+1];
for(int i=0; i<=n; i++) { //모든 노드가 자신을 부모로하는(대표자) 집합으로 만듦
parents[i]=i;
}
}
static int find(int a) { //a의 대표자 찾기
if(parents[a]==a) return a;
return parents[a]=find(parents[a]);
}
static boolean union(int a, int b) { //리턴값: true ==> union성공
int aRoot = find(a);
int bRoot = find(b);
if(aRoot == bRoot) return false;
parents[bRoot] = aRoot;
return true;
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int T=Integer.parseInt(st.nextToken());
for(int test=0; test<T; test++) {
st = new StringTokenizer(br.readLine());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
make();
System.out.printf("#%d ",test+1);
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int go=Integer.parseInt(st.nextToken());
int a=Integer.parseInt(st.nextToken());
int b=Integer.parseInt(st.nextToken());
if(go==0) {
union(a,b);
}
if(go==1) {
if(find(a) == find(b)) {
System.out.print(1);
}
else {
System.out.print(0);
}
}
}
System.out.println();
}
}
}
이와 같은 연산은 MST, PRIM, KRUSKAL 알고리즘에서 활용 될 수 있다.
댓글