[알고리즘] 서로소 집합 - make, union, find 연산

서로소 집합

• 중복 포함된 원소가 없는 집합.
• 집합에 속한 하나의 특정 멤버인 '대표자'로 집합 구분
• 연결리스트 or 트리로 표현
• 서로소 집합 연산
  • Make-Set(x) : 유일한 멤버 x 포함하는 새로운 집합 생성
  • Find-Set(x) : x 포함하는 집합 찾기
  • Union(x, y) : x와 y 를 포함하는 두 집합을 통합하는 연산.
                    x와 y 중 x를 대표자로 설정한다면 x는 y의 부모가 됨.

---

< 서로소집합을 트리로 표현 >

• 하나의 집합 = 하나의 트리
• 자식 노드가 부모 노드 가리킴. 루트 노드가 대표자
• 대표자 노드는 자기자신을 가리킴.

---

<  Union 연산 효율 높이기 >

• Rank 사용 : 각 노드는 자신을 루트로 하는 subtree의 높이를 Rank로 저장
• Path Compression : Find-Set 할 때 만나는 모든 노드들이 직접 root 가리키도록 포인터 바꾸기

---

< 배열로 표현 >

void make() {
  parents = new int[N+1];

  for (int i = 1; i <= N; i++) 
  	parents[i] = i;
}

int find(int a) {
  if(parents[a]==a) return a;
  
  return parents[a] = find(parents[a]);	//  Path Compression
 //return find(parents[a]);
}

void union(int a, int b) {
  int aRoot = find(a);
  int bRoot = find(b);

  if(aRoot != bRoot)	parents[bRoot] = aRoot;
}

find에서 return find(parents[a]); 를 하지 않고 return parents[a] = find(parents[a]); 하는 이유는

path compression 으로 접근 시간을 줄이기 위함이다.

예로 들어

1의 부모 1 , 3의 부모 1, 5의 부모 3 이라면

5의 부모인 3, 또 3의 부모인 1을 찾으려면 여러번 거쳐야하니 find()를 실행할 때

5의 root 부모 1로 바꿔주는 것.