Disjoint-set & Union-Find : 유니온 파인드

Union-Find

서로소, 상호배타 집합이란 서로 중복 표현된 원소가 없는 집합을 의미합니다.

이런 집합을 표현하기 위해서 "대표자" 라는 개념이 도입되는데, 이 대표자를 기준으로 각 집합을 구분할 수 있습니다.

 

이런 상호베타 집합에서 사용할 수 있는 연산은 아래 세가지로 분류됩니다.

 

- make : 단위집합을 만드는 연산 (초기화 함수)

- find : 어떤 한 element가 주어졌을 때, 그 element의 대표자를 구하는 연산.

- union : 두 구성요소가 주어지고, 그 두 구성요소의 각 상호배타 집합을 합치는 연산. 

 

make는 이런 상호배타 연산을 하기 위해 초기셋팅하는 값입니다.

(보통 상호배타집합이 주어지지 않고, 초기에 make()로 모든 엘리먼트를 상호배타집합으로 만든 뒤, 합쳐가며 원하는 집합 구조를 만들어간다)

 

 

간단하게 연산이 어떻게 동작할지에 대한 과정을 정리해보면..

 

1. Make연산

 

각 서로소 집합을 만듭니다.

 

2. Union 연산

인자로 주어진 두 element를 합칩니다. 이때, 새로운 서로소 집합의 대표자는 1로 설정해줬습니다. (편의상..)

 

3. Find 연산

 

find연산을 통해서 1번이 속한 집합의 대표값은 1이라는것을 알 수 있습니다.

find(2) 역시 1을 반환해야합니다.

 

Union-Find 자료구조

Union-Find는 링크드 리스트 자료구조, 트리 자료구조를 활용해서 구현해볼 수 있습니다.

각각의 장단점이 있습니다.

 

링크드리스트

연결리스트는 아래와 같은 구조를 가지고 관리할 수 있습니다.

1. 대표자노드는 항상 head에 위치하도록 관리하고,

2. 추가되는 노드들은 tail에 추가되도록합니다.

3. 그리고 대표자노드가 아닌값은 모두 대표자값에 링크를 한개씩 두어서 대표자 노드를 가리킬 수 있게 합니다.

그럼 이 링크드 리스트를 통해서 위에서 제시했던 연산을 제대로 구현할 수 있는지 생각해봅니다.

 

1. find연산

find연산은 각자 대표자 노드로 연결되는 링크가 있습니다. 그 링크를 활용합니다.

 

2. union연산

union(x,y)라고 했을 때

y가 속해있는 집합을 x가 속해있는 집합으로 편입한다고 가정해보겠습니다.

 

1) 그럼 x가 속해있는 집합의 뒤에 y가 속해있는 집합을 붙여주고,

2) 대표자 노드 링크를 새롭게 업데이트해줍니다.

 

트리

트리는 직관적으로 표현할 수 있습니다.

지금 표현하려는 자료의 형태들이 하나의 자료 밑에 자료들이 저장되는 느낌이라, 트리로 표현하면 조금더 쉽게 표현이 가능합니다.

 

 

위와 같은 형태로 표현하면, 루트노드가 항상 대표자 노드라고 생각하면됩니다.

링크드리스트 방식은 각 노드들이 어떤 대표자노드를 가리켜야할지 생각해야 하는 부분이 있는데,

트리로 풀면 그 트리에 속하는 한 루트로 타고 타고 올라가면되니까, 링크드 리스트에서 가지고 링크관리의 요소가 사라집니다.

 

자세한 예시로 알아보겠습니다.

예를들어 이렇게 X,Y 두개의 서로소 집합이 있고 union(b,y)를 한다고 하면,

y쪽 트리를 b의 부모인 x쪽에 붙여주기만 하면 됩니다. 그럼 c,d,y모두 최상위 루트인 X를 찾으면 되기 때문에, find, union 모두 성공적으로 수행할 수 있습니다.

 

 

Path 가 길어지는 문제.

이런 경우 Path가 길어지는 문제를 만날 수 있습니다.

예를들면 아래와 같은 경우입니다.

최악의 경우 O(N)인데, 사실 이런경우는 이상적인 상황은 아닙니다.

부모를 찾아가는 단계가 많아진다는 뜻이고, 이를 저격하는 테스트 케이스가 나오면 시간초과, 스택오버플로우가 날 수 있는 상황입니다.

 

 

간단하게 이 문제를 개선하는 방법을 설명하자면,

- Rank

rank는 subtree의 길이를 나타내는 지표입니다.

rank를 통해서 subtree의 길이가 짧은것이, subtree의 길이가 높은것에 편입되도록 합니다.

 

예를들어,

두개의 노드가 있다고 하면 각 랭크는 1, 2씩입니다.

 

 

두개의 트리를 합치는 union(2,3)을 수행하면 rank 2가 높으므로, 3에서 2로 합쳐지는게 아니라 2에서 3으로 합쳐집니다.

더 낮은 높이의 subtree에 더 높은 높이의 subtree가 합쳐지면 필수부가결하게 전체 tree의 길이가 높아진다는 특성을 해결하기 위한 방법입니다. (2높이의 트리 -> 1높이의 트리 자식으로 추가 => 여전히 2높이, 반면, 1 높이의 트리에 자식으로 2높이 트리 추가 => 3높이)

 

- Path Compression.

자식들의 부모를 항상 최대 루트로 바꿔주는 작업.

현재 위 트리에서 find(4) 를 하게 되면 1이 나오게 됩니다.

그러면 여기서 자식의 다음 부모 노드를 1로 바꿔줍니다.

그러면 전체적인 subtree의 길이가 줄었습니다!

기존 서로소 집합의 의미를 깨지도 않으면서, 자식이 새로 붙을 때, 다음 작업에서 더 길이가 늘려지는것을 방지하는 방법입니다.

하지만 앞의 경우처럼 Path-Compression 방법으로만은 Path가 길어지는 문제를 해결할 수 없습니다.

결국 줄여야 하는 노드를 대상으로 find를 불러야 의미있는 방법이라고 할 수 있겠습니다.

 

구현

유니온 파인드의 구현은 매우 간단합니다.

보통 링크드리스트의 방식이 아닌 구현의 간단함 때문에 트리 형식을 씁니다.

트리 표현은 1차원 배열로 표현합니다.

 

parent[i] = j

- i : 자식 노드 인덱스 번호.

- j : 부모 노드 인덱스 번호.

 

rank추가버전인데, rank는 길이를 매번 재서 업데이트해주는 방식입니다.

path comparison 을 할 때 마다 rank를 업데이트 해주지 않아서  완벽하지 않지만, 적어도 사용했을 때 어느정도 find()호출 횟수를 줄여주는 효과가 있습니다.

특히 아래에 첨부해놓은 종교 문제같은경우 저격 테스트 케이스가 있기 때문에 이런 솔루션을 활용하지 않으면 문제가 생길 수 있습니다.

 

몇가지 변형 팁.

1. 집합의 크기를 알고 싶은 경우

집합의 크기를 알고 싶은 경우 간단하게 부모노드만 -로 표현하는 방법이 있습니다.

앞써 적용한 Rank방식 대신 집합 크기를 기준으로 union 될 방향을 결정하는것도 좋은 방법일거라 생각됩니다.

물론 이것도 완벽한 방식은 아닐것입니다.

 

1-1)  나머지는 동일하지만 최상위 루트노드는 -로 표기해 둡니다.

1-2) 최상위 루트노드의 절대값은 집합의 크기를 의미합니다.

- 그럼 이제 최상위 노드의 절대값은 항상 최상위 노드 아래 포함되어있는 노드의 개수를 의미합니다.

- 노드의 집합 크기가 더 큰 노드에 노드의 집합크기가 더 작은 노드를 포함시키면 역시 마찬가지로 find() 호출횟수를 줄여주는 방식이 될 수 있습니다.

 

 

관련문제 : 

jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1136&sca=40

JUNGOL

참고하기 좋은 블로그:

blog.naver.com/PostView.nhn?blogId=kks227&logNo=220791837179

유니온 파인드(Union-Find) (수정: 2020-08-03)

 

 

 

 

그래프 시리즈 - 1

- BFS

- BFS 응용

- DFS

 

그래프 시리즈 - 2

- 다익스트라

- union-find

- MST - 크루스칼

- MST - 프림

 

그래프 시리즈 - 3

- 위상정렬

- 플로이드 와샬

 

DP 시리즈

- 일반 DP

- Knapsack

- Subset sum