유니온 파인드 알고리즘

• 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들
  • 교집합이 없음
• 대표자(repersentative)
  • 집합을 구별하는 데 쓰일 수 있는 해당 집합의 특정 멤버
• 서로소 집합 연산(Union-Find Algorithm)
  • Make-set(x)
    • 원소 1개짜리의 단위 집합을 만듦

    void make_set() {
    	for(int i = 1; i <= parents.length; i++) {
    			parents[i] = i;
    	}
    }
    

  • Find-set(x)
    • x가 속한 집합을 찾기
    • x가 속한 집합의 대표자를 반환

    int find_set(int x) {
    	if(x == parents[x]) return x;
    	return parents[a] = find_set(parents[a]);
    }
    

  • Union(x,y)
    • 두 원소가 속한 집합을 합침
    • 두 원소가 속한 집합의 대표자가 다르면 합치기 가능

    boolean union(int a,int b) {
    		int aRoot = find(a);
    		int bRoot = find(b);
    		if(aRoot == bRoot) return false;
    		
    		parents[bRoot] = aRoot;
    		return true;
    	}
    

• 서로소 집합을 표현하는 방법
  • 연결 리스트
    • 같은 집합의 원소들은 하나의 연결리스트로 관리
    • 연결리스트의 맨 앞의 원소를 집합의 대표 원소(대표자)로 삼음
    • 각 원소는 집합의 대표 원소를 가리키는 링크를 가짐
  • 트리
    • 하나의 집합(a disjoint set)을 하나의 트리로 표현
    • 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨
    • 연산 예시
      • 주어진 트리들에 나온 모든 원소를(a~f 라 가정) make-set 연산을 진행하여 각각 개별 집합으로 선언
        • Make-set(a) ~ Make-set(f)
      • Union(c,d) // Union(e,f) =⇒ (c, d) , (e, f) 집합 생성
• 서로소 연산 효율을 높이는 방법
  • Rank를 이용한 Union
    • 각 노드는 자신을 루트로 하는 Sub Tree의 높이를 랭크(Rank)라는 이름으로 저장
    • 두 집합을 합칠 때 Rank가 낮은 집합을 Rank가 높은 집합에 붙임
  • Path Compression
    • Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 Root를 가리키도록 포인터를 바꿔줌