티스토리 뷰

Union-Find 란?

Union-Find 란?

Union-FindDisjoint Set 을 표현할 때 사용하는 독특한 형태의 자료구조로,

공통 원소가 없는, 즉 "상호 배타적" 인 부분 집합 들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

입니다.

위의 상황을 표현하기 위해서는 초기화 과정과 다음과 같은 두 가지 연산을 지원해야 하기 때문에, Union-Find 자료구조 라고 부르게 되었다고 합니다.

Union-Find 지원 연산

  1. 초기화 : N 개의 원소가 각각의 집합에 포함되어 있도록 초기화 합니다.

  2. Union (합치기) 연산 : 두 원소 a, b 가 주어질 때, 이들이 속한 두 집합을 하나로 합칩니다.

  3. Find (찾기) 연산 : 어떤 원소 a 가 주어질 때, 이 원소가 속한 집합을 반환합니다.


Union-Find 의 구현

Union-Find의 실제 구현은 주로 트리구조를 이용하는데, 왜 배열은 이용하지 않는지, 트리를 사용하였을 때의 장점은 무었인지에 대해 알아보도록 하겠습니다.


배열로 표현하기

가장 간단한 방법으로 1차원 배열로 집합을 표현합니다.

예를 들어

번 원소가 속하는 집합의 번호

라 하면

Union-Find 지원 연산

  1. 초기화 : 와 같이 각자 다른 집합 번호로 초기화 해줍니다.

  2. Union (합치기) 연산 : 두 집합을 합치기 위해 배열의 모든 원소를 순회 하면서 하나의 집합 번호를 나머지 한개의 집합 번호로 교체합니다. 아래의 그림은 3번 집합을 2번 집합으로 합치는 과정입니다. (  


  1. Find (찾기) 연산 : 한 번만에 원소가 속하는 집합 번호를 알 수 있습니다. ( )

배열로 Union-Find를 구현 할 수는 있지만, 위에서 보았듯 Union 연산 수행 시 배열의 모든 원소를 순회해야 하기 때문에 시간복잡도가 이 됩니다.
물론 Find 연산은 빠르지만, Union 연산 수행 횟수가 많기 때문에 우리는 더 빠른 Union 연산을 원합니다.
더 좋은 방법은 없을까요?


트리로 표현하기

바로 트리Union-Find 를 구현하면 배열보다 빠르게 Union 연산을 수행할 수 있습니다.
세 가지 연산에 대해 알아보기 전에, 트리 구조로 표현하기 위해 필요한 기본적인 내용을 먼저 알아 봅시다.

Base 1
한 집합에 속하는 원소들을 하나의 트리로 묶어주기 때문에, 자료구조는 아래 그림과 같이 트리 들의 집합으로 표현됩니다.

Base 2
트리 구조 에는 트리의 대표 노드 라고도 볼 수 있는 루트 노드 가 존재 하므로, 각 원소가 속하는 집합 번호를 바로 이 루트 노드의 원소로 정합니다.

Base 3
Union 연산을 수행하기 위해서는 두 원소가 같은 집합에 속하는지를 먼저 확인한 후, 다른 집합에 속할 때만 합쳐야 합니다.
같은 집합에 속한다는 뜻은, 같은 루트 노드를 가진다는 말과 대응되므로 어떤 원소의 루트 노드 를 찾는 Find 연산을 지원해야 합니다.

Base 4
이러한 Find 연산을 지원하기 위해서 모든 자식 노드가 부모에 대한 포인터 정보를 가지고 있도록 합니다. 이러한 설정은 가진 정보를 바탕으로 포인터를 따라가 결과적으로 최종 부모인 루트 노드 가 무었인지 찾을 수 있게 됩니다.
단, 부모 노드에서 자식 노드로 내려가는 일은 발생하지 않기 때문에, 부모가 자식에 대한 포인터 정보는 가질 필요가 없습니다.

이를 바탕으로 지원해야 하는 연산을 알아봅시다.



Union-Find 지원 연산

  1. 초기화 : 모두 각자 다른 집합이 됩니다. 각 노드는 모두 루트 노드 가 되며 N 개의 루트 노드를 생성하고 자기 자신을 가리키는 포인터를 가지도록 설정합니다.
  2. Union (합치기) 연산 : 각 트리의 루트를 찾은 뒤, 다르다면 하나를 다른 한쪽의 자손으로 넣어 두 트리를 합칩니다.


  3. Find (찾기) 연산 : 각 노드에 저장된 포인터 정보를 따라가 주어진 원소가 포함된 트리의 루트 노드를 찾습니다. ( 트리의 높이와 시간복잡도가 비례 )


이와 같이 Union-Find트리 구조로도 나타내 보았습니다. Find 연산 수행 시 걸리는 시간이 트리의 높이 와 비례하게 되고, Union 연산 수행시간 역시 Find 연산 수행 시간이 지배하게 됩니다.
이처럼 Union 연산시간 복잡도가 배열로 나타내었을 때의 보다 줄어 들었음을 알 수 있습니다.


트리로 표현하기 : 실제 소스코드


최적화 하기

이와 같이 트리로 구현하는 방법에는 큰 문제점이 발생할 수 있습니다.
바로 최악의 경우 완전히 비대칭 적인 트리, 즉 연결 리스트 형태가 되어버릴 수 있다는 것입니다.
예를 들어 두 트리 a 와 b 를 합칠 때, a 의 루트 노드를 항상 b 의 루트 노드의 자식으로 넣는다고 가정한다면, 다음과 같이


원소의 갯수가 일때, 트리의 높이가 인, 트리의 장점을 전혀 살릴 수 없는 연결 리스트 형태가 되고 맙니다.
이렇게 되면 Union 연산도, Find 연산도 수행시간이 이 되어버려 배열로 구현했을 때 보다도 효율이 나빠지게 됩니다.

이 문제는 두 트리를 합칠 때, 항상 높이가 더 낮은 트리를 높은 트리 밑에 넣음 으로써 해결가능 합니다. 이렇게 되면 트리의 높이가 크게 높아지는 상황을 방지 할 수 있습니다.

이러한 최적화를 union-by-rank 라 하며, 여기서 rank 는 해당 트리의 높이를 저장합니다.


최적화 하기 : 실제 소스코드



위의 코드에서 경로 압축 최적화 ( path compression ) 과정도 함께 추가 되었는데, 이를 수행하면 다음 그림과 같습니다.



Union-Find 정리

위의 최적화 과정을 모두 적용한 Disjoint Set 의 연산 수행시간은 분석하기 아주 어렵습니다. 왜냐하면 Find 연산을 호출 할 때마다 수행시간이 달라지기 때문입니다. ( 트리의 높이 변화에 의해 )

참고한 책에 의하면 평균 수행시간은 로, 여기서

은 에커만 함수를 이용해 정의되는 함수

로 거의 모든 크기의 에 대해 4 이하의 값을 가진다고 합니다. 즉, 현실적인 모든 입력에 대해 상수시간에 동작한다고 봐도 무관 하다고 합니다.

이처럼 Union-Find 는 그 자체로 구현이 매우 간단하고 동작 속도가 아주 빠르기 때문에 다른 알고리즘의 일부로 자주 사용됩니다.

추가적으로

  1. 그래프의 연결성 확인 ( 크루스칼 알고리즘 등 )
  2. 가장 큰 집합 추적

등의 문제에 Union-Find 를 적용하여 해결해 보시기 바랍니다.


[알고리즘 문제해결전략 책을 참고해서 작성했습니다]


댓글
댓글쓰기 폼