[알고리즘] 상호 배타적인 집합 처리 ( 유니온 파인드 : union-find )

 

◇  설명

   □  정의, 특징

      ●  상호 배타적인 집합 ( Disjoint set )

        -  두 집합의 교집합은 공집합  ☞  서로소 집합
        -  최소 신장 트리를 위한 크루스칼 알고리즘 등에서 필요

   □  연산

      -  임의의 원소가 어느 집합에 속하는지 알아내는 연산
      -  두 집합을 합하는 연산

• Make-Set(x)  :  원소 x로만 구성된 집합을 만든다
• Find-Set(x)  :  원소 x를 가진 집합을 알아낸다
• Union(x, y)  :  원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다

   □  방법

     #  연결 리스트 이용

• Make-Set(x)  --  원소 하나로 구성된 집합을 만드는데, 대표 노드 포인터는 자신을 가리키도록 하고, 다음 노드 포인터는 NULL로 지정한다.
• Find-Set(x)  --  원소 x가 가리키는 대표 노드를 리턴한다.
• Union(x, y)  --  원소 x가 속한 집합과 원소 y가 속한 집합을 합친다.
                          Find-Set(x)와 Find-Set(y)로 원소 x, y가 속한 집합의 대표노드를 각각 구한 후
                          두 집합 중 하나(부집합)를 다른 집합(주집합) 뒤에 붙임.
                          주집합의 tail 노드의 다음 노드 포인터를 부집합의 대표 노드를 가리키게 한다.
                          부집합의 모든 노드의 대표 노드 포인터가 주집합의 대표 노드 포인터를 가리키도록 바꾼다.

     #  트리 이용

• Make-Set(x)  --  자식 노드가 부모 노드를 가리키게 한다. 대표 노드가 루트 노드가 된다. 루트 노드의 부모 노드는 자기 자신이다.
• Find-Set(x)  --  원소(노드) x가 속한 트리의 루트 노드를 리턴한다.
• Union(x, y)  --  원소 x가 속한 집합과 원소 y가 속한 집합을 합친다.
                          Find-Set(x)와 Find-Set(y)로 원소 x, y가 속한 집합의 대표 노드를 각각 구한 후
                          두 집합 중 하나(부집합)의 루트 노드(대표 노드)의 부모 노드를 다른 집합(주집합)의 루트 노드(대표 노드)로 설정한다.

       *  랭크( Rank ) 이용  →  연산 효율 높이기
         -  각 노드는 자신을 루트로 하는 서브 트리의 높이를 랭크( rank )라는 이름으로 저장
         -  단 하나의 노드로 된 트리의 높이는 0이라고 정의
         -  루트 노드의 랭크가 해당 집합의 랭크가 된다
         -  두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다
          ( 두 집합의 랭크가 동일한 경우 합칠 때 합집합의 랭크가 커짐 )

 

◇  코드

  ▷  트리 이용

	int p[];

	public void make(int n) {
		for (int i = 0; i < n; i++)
			p[i] = i;
	}

	public int find(int x) {
		return x == p[x] ? x : find(p[x]);
	}

	public void union(int a, int b) {
		a = find(a);
		b = find(b);
		if (a != b)
			p[b] = a;
	}

  ▷  트리 이용  +  랭크 이용, 경로 압축  →  연산 효율 높이기

	int[] p, r;

	public void make(int n) {
		for (int i = 0; i < n; i++) {
			p[i] = i;
			//r[i] = 0;
		}
	}

	public int find(int x) { // 경로 압축
		return x == p[x] ? x : (p[x] = find(p[x]));
	}

	public void union(int a, int b) { // 랭크 이용
		a = find(a);
		b = find(b);
		if (r[a] > r[b])
			p[b] = a;
		else {
			p[a] = b;
			if (r[a] == r[b])
				r[b]++;
		}
	}