서로소

서로소 집합(Disjoint-set)

• 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 즉, 교집합이 없다.
• 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이를 대표자라고 한다.
• 서로소 집합을 표현하는 방법
  • 연결리스트
  • 트리
• 서로소 집합 연산
  • Make-Set(int x)
  • Find-Set(int x)
  • Union(int x, int y)

서로소 집합 예시

서로소 집합 표현 - 연결리스트

• 같은 집합의 원소들은 하나의 연결리스트로 관리
• 연결리스트의 맨 앞의 원소를 집합의 대표 원소(대표자)로 삼는다.
• 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.
  

서로소 집합 표현 - 트리

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

서로소 집합을 표현한 트리의 배열을 이용한 저장된 모습

인덱스	0	1	2	3	4	5
정점	a	b	c	d	e	f
부모 인덱스	0	1	2	2	2	4

서로소 집합에 대한 연산

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

public static void makeSet() {
	parents = new int[N];
    for(int i=0; i<N; i++) {
    	parents[i] = i;
    }
}

• Find-Set(int x) : x를 포함하는 집합을 찾는 연산(x의 대표자를 찾는)

public static int findSet(int x) {
	if(x == parents[x]) {
    	return x;
    }
    
    return parents[x] = findSet(parents[x]);
}

• Union(int x, int y) : x와 y를 포함하는 두 집합을 통합하는 연산

public static boolean Union(int x, int y) {
	
    int xRoot = findSet(x);
    int yRoot = findSet(y);
    
    // 이미 통합된 집합인 경우
    if(xRoot == yRoot) {
    	return false;
    }
    
    parents[yRoot] = xRoot;
    return true;
}

연산의 효율을 높이는 방법

• Rank를 이용한 Union
  • 각 노드는 자신을 루트로 하는 subree의 높이를 rank로 저장
  • 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙이는 방법
• Path compression
  • Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꿔준다.

랭크를 이용한 Union에서 랭크가 증가하는 경우

Path Compression을 이용한 경우

Path Compression 적용한 Find-Set 연산

• 적용 전

Find-Set(x)
if x == parents[x] : return x

else : return Find-Set(parents[x])

• 적용 후

Find-Set(x)
	if x == parents[x] : return x
    
    else : return parents[x] = Find-set(parents[x])