상호배타적 집합 · 유니온 - 파인드 → 크루스칼 · 프림 → 다익스트라 · 벨만-포드 알고리즘
집합이란?
집합은 순서와 중복이 없는 원소들을 갖는 자료구조를 의미한다.
예를 들어 A라는 그룹의 원소가 {1, 6, 6, 6, 4, 3} 이라면 이는 집합으로 생각할 때 중복을 제외해 {1, 6, 4, 3}으로 생각할 수 있다.
순서를 고려하지 않으므로 {6, 1, 3, 4}와 같다고 볼 수 있다.
집합의 종류
집합은 특성에 따라 여러 종류의 집합으로 나뉜다.
- 유한 집합 : 원소의 개수가 유한 개인 집합
- 무한 집합 : 원소의 개수가 무한 개인 집합
- 공집합 : 아무런 원소가 없는 집합
등.. 이 있다.
상호배타적 집합(Disjoint Sets)이란?
이후 계속 언급하는 집합은 상호배타적 집합이다.상호배타적 집합은 교집합이 없는 집합 관계를 말하며 서로소 집합이라고도 한다.
교집합이 없다는게 어떤 의미일까?
그림의 왼쪽과 같이 집합 A = {1, 2}, 집합 B = {3, 4} 라고 하자.
이렇게 집합 A와 집합 B의 원소 중 겹치는 원소가 없으면 교집합이 없다고 할 수 있고, 이를 상호배타적 집합이라고 한다.
반면, 그림의 오른쪽과 같이 집합 C = {1,2}, 집합 D = {2, 3} 이라고 한다면
공통된 원소 2가 존재하기 때문에 상호배타적 집합이라고 할 수 없다.
상호배타적 집합의 활용
어디에 쓰이길래 상호배타적 집합을 알아야 하는 것일까?
그래프 알고리즘에서 사이클을 확인하는 일이 많은데 이때 상호배타적 집합 개념이 활용한다.
그 외에도 다음과 같은 알고리즘 문제들에서 상호배타적 집합을 활용할 수 있다.
- 이미지 분할 : 이미지를 서로 다른 부분으로 나눈데 사용한다.
ex. 사람과 배경을 겹치지 않게 분할하는데 사용될 수 있다. - 도로 네트워크 구성 : 도로를 구축할 때 각 도로를 서로 교차하지 않도록 설계하는데 사용할 수 있다. 이를 통해 교차로의 혼잡을 줄일 수 있다.
- 최소 신장 트리 알고리즘 : 최소 신장 트리 알고리즘을 구현에서 간선을 추가할 때마다 사이클을 형성하는지 여부를 체크할 때 사용한다.
- 게임 개발 : 캐릭터의 동작을 자연스럽게 구현할 수 있다. → 플레이어와 적군이 충돌할 때 두 캐릭터가 겹치지 않도록 하는데 사용할 수 있다.
- 클러스터링 작업 : 각 작업이 서로 겹치지 않도록 구성할 수 있다. 이렇게 작업 간의 의존 관계가 없으면 동시에 여러 작업을 진행할 수 있다.
집합의 연산
어떻게 집합을 표현하고 어떻게 연산을 할 수 있을까?
보통 집합은 트리로 표현하며 대표적인 연산으로는 합치기와 탐색이 있다.
배열을 활용한 트리로 집합 표현하기
집합은 배열을 활용한 트리로 구현하고, 각 집합에는 대표 원소가 있어야 한다.
대표 원소란?
대표 원소는 원소 중 집합을 대표하는 역할을 한다.
집합의 형태를 트리로 표현할 것이기 때문에 대표 원소를 루트 노드라고 한다.
배열을 집합으로 표현하는 것이란?
집합을 배열로 표현한다는 것은 하나의 배열로 상호배타적 관계를 가지는 집합을 모두 표현한다는 것을 의미한다.
그리고 집합을 트리 형태로 표현할 때는 다음을 기억하면 된다.
" 배열의 인덱스는 자신을, 배열 값은 부모 노드를 의미한다. "
예를 들어 disjoint_set[9] = 3 이면 노드 9의 부모 노드가 3임을 의미한다.
루트 노드는 집합의 대표이므로 부모가 없고, 부모 노드가 자기 자신이다.
즉, 루트 노드의 값은 배열의 인덱스와 동일하다.
집합을 표현하는데 사용하는 배열의 크기는 배열의 인덱스가 모든 집합의 원소를 표현할 수 있으면 된다.
유니온 - 파인드 알고리즘
집합 알고리즘에 주로 쓰이는 연산은 합치기와 탐색이다.
합차기는 유니온(union), 탐색은 파인드(Find) 라고 하여 둘이 묶어 유니온-파인드 알고리즘이라고 한다.
파인드 연산
Find 연산은 특정 노드의 루트 노드가 무엇인지 탐색하는 방법이다.
보통 Find 연산은 특정 노드가 같은 집합에 있는지 확인할 때 사용한다.
예를 들어 두 노드 A, B의 루트 노드가 같다면 A, B는 같은 집합에 속해있는 노드이다.
루트 노드를 찾는 방법은 특정 노드부터 재귀로 거슬러 올라가며 루트 노드를 찾았던 과정이며 다음과 같다.
- 현재 노드의 부모 노드를 확인한다.
부모 노드를 확인하다가 부모 노드가 루트 노드이면 찾기 연산을 종료한다.
index == value - 1에서 찾기 연산이 종료되지 않으면 1을 반복한다.
def find(parent, x):
if parent[x] == x: # 자기 자신이 루트 노드라면 반환
return x
return find(parent, parent[x]) # 부모를 따라 루트 노드를 찾음
파인드 연산의 비용 문제 → 경로 압축으로 해결
Find 연산의 경우 현재 노드의 부모 노드를 계속 거슬러 올라가면서 최종 루트 노드를 찾는다. (by 재귀)
그런데 만약 다음과 같은 트리에서 Find 연산을 수행한다면 ?
find(n) 을 수행하면 n번 노드부터 시작하여 부모 노드까지 거슬러 총 n-1번 반복해야 한다.
이러한 경우 딱 봐도 비효율적이고.. 이렇게 트리가 비대칭 구조를 이루는 경우에는 최악의 경우가 되어 시간복잡도가 O(n)이 된다.
이러한 문제에서 좀 더 효율적인 파인드 연산을 하기 위해서는 집합 형태를 유지하면서 트리 높이를 줄이면 된다.
이를 경로 압축(Path Compression)이라고 한다.
경로 압축이란 트리의 루트 노드를 제외한 모든 노드들이 루트 노드의 자식 노드가 되도록 트리를 압축하는 것을 의미한다.
경로 압축 코드는 다음과 같이 수정하여 구현할 수 있다.
def find(parent, x):
if parent[x] != x: # 루트 노드가 아니라면
parent[x] = find(parent, parent[x]) # 루트 노드를 찾고 부모를 직접 설정 (경로 압축)
return parent[x] # 루트 노드 반환
유니온 연산
유니온 연산은 두 집합을 하나로 합치는 연산이다.
두 집합을 하나로 합치는 것은 두 집합의 루트 노드를 같게 하는 것이다.
이때 루트 노드는 두 집합의 루트 노드 중 하나가 되면 된다.
합치는 과정은 다음과 같다.
- 두 집합에서 Find 연산을 통해 루트 노드를 찾는다.
- 찾은 두 루트 노드의 값을 비교한다.
- 두 집합의 루트 노드를 같게 하여 두 집합을 합친다.
이때 루트 노드는 두 집합 중 어떤 노드로 하더라도 상관 없다.
def union(parent, a, b):
rootA = find(parent, a)
rootB = find(parent, b)
if rootA != rootB: # 다른 집합이면 합침
parent[rootB] = rootA # rootB를 rootA에 연결
이때 문제점은 한쪽 루트에 무조건 다른 루트를 붙이기 때문에 트리가 한쪽으로 치우칠 가능성이 있다.
예를 들어 1-2-3-4-5-6 같은 형태가 되면 Find 연산 시 최악의 경우가 되어 시간복잡도가 O(n)이 된다.
유니온 연산의 비용 문제 → 랭크로 해결
기본 union( ) 에서는 항상 하나의 루트에 대해 다른 루트를 밑에 붙이므로 트리가 불균형해질 수 있다.
→ 높이가 깊어지면 Find 연산이 느려진다.
따라서 유니온 바이 랭크 (Union by Rank)로 트리의 높이를 줄일 수 있다.
- 랭크(Rank) : 트리의 높이를 기준으로 작은 트리를 큰 트리에 붙이는 방식
랭크가 낮은 족을 랭크가 높은 쪽에 붙이면 트리의 높이가 줄어 Find 연산이 빨라진다.
# 부모 테이블과 랭크 배열 초기화
def make_set(n):
parent = [i for i in range(n)] # 자기 자신을 부모로 설정
rank = [1] * n # 트리의 높이를 1로 초기화
return parent, rank
# 경로 압축이 적용된 Find 연산
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x]) # 경로 압축 적용
return parent[x]
# 랭크 기반 유니온(Union by Rank)
def union(parent, rank, a, b):
rootA = find(parent, a)
rootB = find(parent, b)
if rootA != rootB: # 서로 다른 집합이면 합침
if rank[rootA] > rank[rootB]: # 더 깊은 트리에 작은 트리를 붙임
parent[rootB] = rootA
elif rank[rootA] < rank[rootB]:
parent[rootA] = rootB
else: # 높이가 같다면 한쪽을 올리고 랭크 증가
parent[rootB] = rootA
rank[rootA] += 1
# 사용 예제
n = 6 # 노드 개수
parent, rank = make_set(n)
union(parent, rank, 0, 1)
union(parent, rank, 1, 2)
union(parent, rank, 3, 4)
union(parent, rank, 4, 5)
print(find(parent, 0)) # 0과 연결된 루트 노드 출력
print(find(parent, 2)) # 같은 집합이면 동일한 루트 노드 출력
print(find(parent, 3)) # 3과 연결된 루트 노드 출력
print(find(parent, 5)) # 5도 동일한 루트 출력
유니온 바이 랭크 적용 후 성능 비교 (최악의 시간 복잡도)
| 기본 유니온 | O(N) |
| 경로 압축 적용한 Find | O(α(N)) (거의 O(1)) |
| 유니온 바이 랭크 적용한 유니온 | O(α(N)) (거의 O(1)) |
📌 α(N) (역 아커만 함수)
- 거의 상수 시간에 가깝게 동작하는 매우 느리게 증가하는 함수
- 현실적인 범위(10⁹ 이하)에서는 O(1)과 유사한 성능을 보인다.
reference
코딩테스트 합격자되기
https://blogshine.tistory.com/103
https://lotuslee.tistory.com/106
'알고리즘' 카테고리의 다른 글
| [알고리즘] 다익스트라(Dijkstra) 알고리즘 (0) | 2025.04.03 |
|---|---|
| [알고리즘] 그래프 (Graph) - 2. 그래프 탐색 (0) | 2025.02.19 |
| [알고리즘] 그래프 (Graph) - 1. 개념 (0) | 2025.02.14 |
| [알고리즘] 투포인터 (Two Pointers) (0) | 2025.02.14 |
| [알고리즘] 우선순위 큐 (0) | 2025.02.11 |
