(자료구조 & 알고리즘 정리) 서로소집합, 유니온파인드 (2023.06.24)

1. 서로소 집합

---

1) 개념

- 집합 A와 집합 B에 공통된 원소가 존재하지 않으면 A와 B를 서로소 집합이라고 함

2) 서로소 집합 표현 방법

- 연결리스트

- 트리

3) 연산

- Make-Set(x) : 유일한 멤버인 x를 포함하는 새로운 집합을 생성하는 연산

//슈더
	//p[x] : 노드 x의 부모 저장
	//rank[x] : 루트 노드가 x인 트리의 랭크 값 저장
Make-Set(x) {
	p[x] = x
	rank[x] = 0;
}
// for(i=1; i<=6; i++) make-set(i) 를 하면 배열 채워짐.
// 굳이 p[i] = x인 반복문 코드를 활용해도 가능. 
//명시적으로 Set을 만든다는 의미 부여를 위한 메서드

- Find-Set(x) : x가 속한 그룹의 대표자를 찾는 연산

Find-Set(x)
	if x==p[x] return; //p[x]는 x의 대표
	else return Find-Set(p[x]); //여기에 x를 그대로 넣으면 무한 호출이 됨.

- Union(x,y) : x, y를 하나의 그룹으로 만들기

Union(x,y)
	Link(Find_Set(x), Find_Set(y));

Link(x, y)
	if rank[x] > rank[y]:
		p[y] = x;
	else 
		p[x] = y
		if(rank[x] == rank[y] :
				rank[y] ++;

 

4) Union 연산의 효율을 높이기 

- 기존 코드

//슈더
Union(x,y)
	p[Find-Set(y)] = Find-Set(x)
//x의 집합이 들어가는 건가 y의 집합이 x로 들어가는건가?
//y의 집합이 x로 들어가는 것.
//y의 대표를 가져와서 그 대표가 가리키는 값을 x의 대표로 갈아끼운 것이므로.

- 효율 높인 후 코드

Union(x,y)
	Link(Find_Set(x), Find_Set(y));

Link(x, y)
	if rank[x] > rank[y]:
		p[y] = x;
	else 
		p[x] = y
		if(rank[x] == rank[y] :
				rank[y] ++;

 

- 아래 코드가 더 효율적인 이유

• 문제점 : 중복된 호출이 일어난다. 균형있게 트리가 만들어지면 좋을 텐데, 한쪽으로만 쭉 있는 편향트리가 되면 그 또한 비효율적
• 연산의 효율을 높이는 방법
  • Rank를 이용한 Union
    • 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크(Rank)라는 이름으로 저장함
    • 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙임
    • 이렇게 하면 높이 변화 발생하지 않음.
    • 높이가 똑같다면 아무 곳에 붙여도 상관 없지만, 붙이고 나서 붙인 쪽의 rank값을 하나 올려줘야 함.
  • Path compression
    • Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸어 줌.
    • 코드 간단해서 자주 사용하게 될 것.
    • 피보나치 했을 때 기록했던 방식을 떠올려 보면 좋겠다 !!

 

2. 관련 문제

---

1) 

 

 

 

---