[알고리즘] Union-Find

개념

• 그래프 이론으로, 상호 배타적 집합(서로소집합:Disjoint-Set) 알고리즘이라고도 부름
• 주로 크루스칼(Krusckal) 알고리즘에서 사용하며, 순환하지 않는 트리 를 만들기 위해 사용

단계별로 이해하기

1. 만약 아래 표와 같이 4개의 노드를 가진 서로소 집합이 있다면, 

   노드 번호	1	2	3	4
   대표 번호	1	2	3	4

2.  1번과 2번이 같은 집합이라면?
   • 대표번호를 변경하여 같은 집합을 표현할 수 있음
   • Union
   • 결과

     노드 번호	1	2	3	4
     대표 번호	1	1	3	4

3. 아래 표와 같이 있을 때 2번은 어떤 집합에 있는지 알 수 없을까?

   노드 번호	1	2	3	4
   대표 번호	1	3	4	1

   • 노드 번호를 따라가며 확인할 수 있음
     • 2번 👉 3번 👉 4번 👉 1번 (모두 같은 집합)
   • Find
   • 다른 표현

     노드 번호	1	2	3	4
     대표 번호	1	1	1	1

 

 

구현

단계

1. Make (Root 배열 생성)
2. Find (spot `x` 에 대한 root spot 찾기)
3. Union (spot `x`와 spot `y` 를 합하여 하나의 집합으로 만들기)

 

1. Make()
   • 부모 노드를 저장할 배열 생성
2. Find()
   • 부모 노드 배열을 이용하여 자신의 Root를 찾아감
   • 재귀를 활용하여 구현(배열로 사용하는 것보다 빠름)
     • 빠른 이유
3. Union()
   • 서로 다른 두 트리(집합)을 하나의 트리(집합)으로 묶음
   • Find() 함수를 이용하여 서로의 부모가 다른 경우 두 노드를 연결
4. ✔ 부모 노드 배열을 Root 배열로 변환하여 최적화 해보자
   • Find() 함수를 구현 시, Root 배열에 저장하며 찾아가기

시간 복잡도

• 총 3가지 과정을 가지고 있어 과정 별로 살펴보자
  1. 초기화
     
     • N개의 값을 갖는 Root 배열이 필요하므로, O(N)
  2. Find
     • 평균적으로 트리의 높이만큼 탐색, O(logN)
     • 사향트리의 경우, O(N)

• 3. Union
  • Find 함수를 사용하여 Find 함수의 시간 복잡도를 따라감

코드

1. make()

# root 배열 생성
parent = [i for i in range(n+1)]

2. Find()

def find(num:int)->int:
	# 대표 번호(Root)가 '나' 이면 끝
    if parent[num] == num:
        return num
    # 대표 번호(Root)를 찾아가면서 지나온 배열에 저장
    parent[num] = find(parent[num])
    return parent[num]

3. Union()

def union(num1:int, num2:int) -> None:
    x = find(num1)
    y = find(num2)
    if x != y:
        parent[y] = x
    return

예제

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

2024.01.07 - [Algorithm/BaekJoon Review] - 1717. 집합의 표현

1717. 집합의 표현

참조

트리를 사용하는 이유

Tree vs Array

1. 표현 방식
Tree
하나의 트리를 같은 집합으로 표현

Array
같은 배열을 같은 집합으로 표현

2. 시간 복잡도
Tree
Make() : O(N)
Union() = Find() = O(N-1) (트리의 높이)

Array
Make() : O(N)
Union() : O(N) (N개의 배열 순회하며 대표 번호 변경)
Find() : O(1) ( 배열 인덱스 읽기)

결론: 시간복잡도가 빠름