[문제해결기법] 8. 서로소인 집합의 표현 (Disjoint Sets)

 

서로소인 집합의 표현 (Disjoint Sets)

• 서로소인 집합 : 전체집합의 부분집합들 중, 둘을 고르면 교집합=공집합, 전체 합집합=U
• U의 두 원소가 같은 부분집합의 원소인지 아닌지 어떻게 알 수 있을까?
• 신장트리 : 그래프 G의 노드를 모두 포함하는, E에 속하는 에지로 만든 트리
• 최소신장트리 : 트리에 속한 가중치의 합이 가장 작은 신장 트리.

 

최소 신장 트리 (MST) 만들기

1. Prim’s algorithm : 현재 집합(노드들)과 연결된 에지 중 가중치가 최소인 것을 MST 집합에 포함시킴.
   1. 구현법에 따라 시간복잡도가 차이남
   2. 다익스트라 알고리즘 = 특정 시작노드부터 다른 노드들까지의 최단거리를 구함. 유/무향 그래프 프림 알고리즘 = 모든 노드들을 최소비용으로 연결 / 두 노드사이의 거리는 최단거리가 아닐 수 있음. 무향 그래프
   3. 매번 남아있는 에지 중 최소를 찾는다면, $O(|V|^2)$
   4. 우선순위 큐를 통해 한번에 $O(log |V|)$ → 반복 시 $O((|V|+|E|) log |V|)$
2. Kruskal’s algorithm : 그리디의 일종, 에지를 오름차순 정렬 후 사이클이 없도록 작은것부터 선택
   1. 정확도는 자명
   2. 쉬운 구현 : 모든 노드에 다른 색을 할당하여, 에지로 연결되면 같은 색으로 다시 칠함. 같은색의 에지를 다시 칠하면 사이클!

서로소인 집합의 표현

• 각 집합을 일종의 트리로 생각, 한 노드에서 루트를 찾아 올라가기
• 두 집합을 합치려면, 가장 높은 노드가 루트가 되고 다른 집합의 루트는 그 루트의 자식으로. (union find)