[알고리즘] 유니온 파인드

서로소 집합

1일 제외한 공통된 약수가 없다.
즉, 교집합이 없다!

집합들이 존재할 때, 각 집합의 하나의 특정 멤버를 통해 각 집합을 구분한다.
이를 대표자(representative)라 한다.

이 대표자가 집합의 식별자 역할을 한다.

서로소 집합 표현

서로소 집합을 표현하는 방법은 2가지

1. 연결 리스트
2. 트리

서로소 집합 연산

1. Make-Set(x) -> 유일한 멤버인 x를 포함하는 새로운 집합을 생성
2. Find-Set(x) -> x가 속해있는 집합의 대표자를 찾는다.
3. Union(x,y) -> x,y 가 속해져있는 각 집합끼리 합친다.

유니온 파인드 문제들은 위 연산 3가지를 통해 문제를 해결할 수 있다.
유니온 파인드 개념을 이해하고, 해당 연산을 이해하고 약간의 외우기가 필요하다.

• Make-Set(x)

Make-Set(x) :
    p[x] = x ;

대표자 배열을 1차원으로 만들어주고, 그걸 p[]라고 하면,
Make-Set(x)는 자기 자신을 집합으로 만들어주는 것이니까,
x 의 대표는 자기 자신일 것이다.

• Find-Set(x)

Find-Set(x) :
	if Find-Set(x) == x :
    	return x;
    else :
    	return Find-Set(p[x]);

대표자를 찾는데, 만약 대표자랑 자기랑 같으면, 그게 대표자죠.
그러니까 자기 자신을 찾으면 x를 return 해주고,
만약 자기 자신이 아니라면, 자기자신의 부모를 파라미터로 넘겨주고 또 대표자를 찾도록 재귀함수를 호출!

• Union(x,y)

	if Find-Set(x) == Find-Set(y) :
    	return;
    p[Find-Set(y)] = Find-Set(x);

두 집합을 통합하면, 각 집합의 대표자들을 찾고, y의 대표자 하위에 있는 모든 집합들을 x의 집합 안에 넣어야 하니까, 위와 같은 코드가 나오게 됨.

유니온파인드 연결 리스트 구현 방법

1. 같은 집합의 원소들을 하나의 연결 리스트로 관리하는 방법
2. 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.
3. 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다.

유니온파인드 트리 구현 방법

1. 같은 집합의 원소들을 하나의 트리로 표현한다.
2. 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.