집합
순서와 중복이 없는 원소들을 갖는 자료구조
상호배타적 집합 : 교집합이 없는 집합 관계
- 그래프 알고리즘에서 많이 활용된다.
- 활용 분야
- 이미지 분할 / 도로 네트워크 구성 / 최소 신장 트리 알고리즘 구현 / 게임 개발 / 클러스터링 작업
앞으로 글의 내용에서 집합을 상호배타적 집합이라 가정한다.
집합의 연산
- 집합의 표현 방법 : 배열을 활용한 트리로 구현
- 집합의 대표적인 연산
- 합치기 (유니온)
- 탐색 (파인드)
- 배열을 활용하여 트리로 집합 표현
- 각 집합 에는 대표 원소가 있어야 한다.
- 집합의 원소 중 집합을 대표하는 역할
- 집합의 형태를 트리로 표현할 것이므로 대표 원소를 루트 노드라 가정한다.
- 하나의 배열로 상호배타적 관계를 가지는 집합을 모두 표현한다.
- 배열의 인덱스는 자신을, 배열값은 부모 노드를 의미한다.
disjointSet[3] = 9: 노드 3의 부모노드는 9- 루트 노드는 부모 노드가 자기 자신이다.
- 배열의 크기
- 배열의 인덱스가 모든 집합의 원소를 표현할 수 있으면 된다.
- ex. 가장 큰 값의 원소가 9인 경우 배열의 크기는 10
- 구현
- 초기 각 노드는 자기자신을 루트 노드로 하고, 집합에 없는 인덱스의 값은 -1로 한다.
- 각 집합 에는 대표 원소가 있어야 한다.
- 유니온-파인드 알고리즘
- 집한 알고리즘에 주솔 쓰이는 연산인 합치기(유니온)와 탐색(파인드)을 묶어 유니온-파인드 알고리즘이라고 한다.
- 이름과 달리 실제로는 파인드 연산부터 진행된다.
- 파인드 연산
- 특정 노드의 루트 노드가 무엇인지 탐색하는 방법
- 특정 노드가 같은 집합에 있는지 확인할 때 사용한다.
- ex. A,B 두 노드의 루트 노드가 서로 같다면 같은 집합에 속한 것이다.
- 현재 노드의 부모를 확인하다가 부모 노드가 루트 노드이면 찾기 연산을 종료한다.
- 루트 노드는 자신과 부모 노드가 같다.
- 이와 같은 탐색 연산은 재귀 함수로 구현한다.
- 최악의 경우 시간 복잡도 : O(N)
- 개선 방법 : 경로 압축
- 효율적인 연산을 위해 집합 형태를 유지하면서도 트리 높이를 줄인다. ⇒ 부모 노드를 거치는 과정을 줄일 수 있다.
출처 : https://lemidia.github.io/data structure/unionfind/
- 유니온 연산
- 두 집합을 하나로 합치는 연산 (두 집합의 루트 노드를 같게 하는 것)
- 이때 루트 노드는 두 집합의 루트 노드 중 하나가 되면 된다.
- 과정
- 두 집합에서 찾기 연산을 통해 루트 노드를 찾는다.
- 찾은 두 루트 노드의 값을 비교한다.
- 두 집합을 합친다. (두 집합의 루트 노드를 같게 한다. 루트 노드는 두 집합 중 어떤 루트 노드로 해도 상관 없다.)
- 트리의 깊이에 비례하여 연산 비용이 커진다.
- 개선 방법: 랭크
- 랭크: 현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이
- 랭크를 기반으로 합치기 연산
- 규칙
- 두 노드의 루트 노드를 구한다.
- 구한 루트 노드의 랭크를 비교한다.
- 랭크 값이 다르면 랭크값이 큰 루트 노드를 기준으로 삼는다. 랭크가 더 큰 루트 노드를 랭크가 작은 루트 노드의 부모 노드로 바꾼다.
- 랭크 값이 같으면 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더한다.
- 규칙
- 두 집합을 하나로 합치는 연산 (두 집합의 루트 노드를 같게 하는 것)
- 특정 노드의 루트 노드가 무엇인지 탐색하는 방법
- 집한 알고리즘에 주솔 쓰이는 연산인 합치기(유니온)와 탐색(파인드)을 묶어 유니온-파인드 알고리즘이라고 한다.
