[ETC] JAVA - Union-Find - 공룡 루디

[ETC] JAVA - Union-Find - 공룡 루디

Union-Find란?

Union-Find는 서로소 집합을 표현할 수 있는 자료구조로

크게 Union과 Find라는 2가지 연산으로 이루어져 있어

Union-Find라고 불립니다.

Union-Find를 구현 위해서는

union이라는 연산과 find라는 연산에 대해 이해할 수 있어야 합니다.

Find 연산의 개념

find 연산의 목적은 어떤 원소가 어떤 집합에 속하여 있는지 알아내는 연산입니다.

예를 들어 a, b, c, d라는 각각의 원소가 있다고 가정할 때

해당 원소가 어떤 집합에 속하여 있는지 알아내는 연산으로

find(a), find(b) 등을 통하여 해당 원소가 어떤 집합인지 알 수 있어야 합니다.

find 연산을 구현하기 위해서는 해당 원소들이 어떤 집합에 포함되어 있는지

알 수 있는 자료구조( 배열, 해시 등)가 있어야 합니다.

각각의 원소가 서로 다른 집합에 포함되어 있다는 가정이 있다면

각 원소의 집합은 A, B, C, D이고

find(a)로는 a원소는 A집합에 포함되어있다.

find(b)로는 b원소는 B집합에 포함되어있다.

find(c)로는 c원소는 C집합에 포함되어있다.

find(d)로는 d원소는 D집합에 포함되어있다.

라는 것을 알 수 있어야 합니다.

Union 연산의 개념

union 연산은 합집합의 개념을 생각하시면 됩니다.

(두 원소가 속하는 두 집합을 합치는 경우로 합집합을 구현합니다.)

두 집합이 서로소 집합이라는 가정이 있을 때

A라는 집합과 B라는 집합이 있고

A와 B를 합치기 위해

집합 B의 원소를 모두 집합 A로 흡수시킨다고 생각하면

집합 B의 모든 원소들이 속한 집합을 집합 A로 바꾼다는 이야기가 될 수 있습니다.

(반대의 경우도 가능 A의 모든 원소를 집합 B로 바꿈)

하지만 실제 union연산을 구현할 때는

집합에 속한 모든 원소가 가리키는 집합을 바꾸는 방법도 있고

대표 원소가 가리키는 집합만 바꾸는 방법도 있습니다.

Find 연산 구현하기

find 연산을 구현하기 위해서는

배열이나 해시 맵을 통해 해당 원소가 어떤 집합에 포함되어있는지 명시할 수 있어야 합니다.

저는 배열을 통해 인덱스로 접근하여 특정 원소가 어떤 집합을 가리키는지

배열로 구현하였습니다.

각 원소가 초기에 모두 서로소 집합이라는 가정이 있을 때

배열의 인덱스와 배열에 저장되어 있는 값은 같습니다 arr[x]=x

이러한 방법은 원소와 집합을 인덱스로 표현할 수 있을 때

편리하게 이용할 수 있습니다.(이렇게 표현이 힘들면 해시 맵을 이용 하면 됩니다.)

예를 들어 1,2,3,4라는 원소 가 있을 때

arr[]은 arr[0]=0;// 채워 넣지 않으면 기본값이 0으로 동일합니다.

arr[1]=1;

arr[2]=2;

arr[3]=3;

arr[4]=4;

로 각 원소가 각각의 집합을 가리키는 상황이 되게 됩니다.(초기 상태)

union(1,2)를 통해 원소 1과 원소 2를 합친다고 가정하면

arr[1]=1

arr[2]=1 로

원소 2가 가리키는 값을 1로 바꿈으로써

원소 2가 1이라는 집합에 포함되어있다고 표현할 수 있습니다.

이때 find(1)을 하면 1을 리턴해야 하고 find(2)를 해도 1을 리턴해야 합니다.

이 상태에서 원소 3과 원소 1을 union 하게 되고

집합 1을 집합 3에 합쳐진다고 가정하게 되면

배열의 상태는

arr[1]=3

arr[2]=1

arr[3]=3

아래와 같은 형태로 바뀔 수 있습니다.

이때 원소 1은 집합 3에 속해 있고, 원소 3은 집합 3에 속해있는데

원소 2는 여전히 집합 1에 속해있는 상태로 저장되어있습니다.

앞서 원소 2의 집합은 집합 1에 속해있는 상태이기 때문입니다.

하지만 find연산에서 원하는 결과는 어떤 원소가 어떤 집합에

속해 있는지 알아내는 게 중요하기 때문에

find(2)를 하면 arr [2]에 속해있는 1을 최종적으로 return 하면

원소 2는 집합 1에 속해있는 걸로 되기 때문에 원하는 결과가 아닙니다.

이러한 문제를 해결하기 위해서는 어떤 집합에 속하는지

recursive 하게 타고 올라가야 합니다.

이를 반영한 코드는 아래와 같습니다.

find(2, arr)을 하게 되면

if문을 통해 x와 arr [x]를 비교하게 되는데

이때 x와 arr[x]가 같다면 x를 리턴하게 됩니다.

하지만 다르다면 다시 find(arr[x],arr)연산을 호출하여 해당 결과를 리턴하게 됩니다.

이렇게 하면 find(2,arr)을 호출하고

원소 2와 arr[2]의 값을 비교하게 됩니다.

하지만 원소 2와 arr[2]은 다른 값을 가지고 있기 때문에

find(arr[2],arr)을 호출하게 되고

이는 find(1,arr)과 같습니다.

또 find(1,arr)에서

1==find[1]은 false이기 때문에

find(arr[1],arr) 즉 find(3,arr)을 호출하고

최종적으로 3을 리턴하여

원소 2는 집합 3에 속하는 원하는 결과가 나오게 됩니다.

union 연산 구현하기

union 연산은 합집합을 의미합니다.

(두 원소가 속하는 두 집합을 합치는 경우로 합집합을 구현합니다.)

아래와 같은 상황에서 원소 1과 원소 3을 합치는 것은

union(1,3)으로 표현하고

원소 2가 속한 집합과 원소 3이 속한 집합을 합치는 것은

union(2,3)으로 표현합니다.

하지만 원소 2가 속한 집합은 1이기 때문에

결과적으로 union(1,3)과 같게 됩니다.

두 원소가 속한 집합끼리 합치는 것을 구현하는 방법은

union 내부에서

두 원소가 속한 집합을 찾고

해당 집합의 대표 원소의 값을 바꾸는 방법이 있습니다.

이 방법을 구현하기 위해서는

union(2,3)이 호출되었다고 가정할 때

원소 2와 원소 3이 속한 대표 집합을 알아야 합니다.

그 방법으로 find(2)와 find(3)이 있고

find(2)를 통해 원소 2는 집합 1에 속하고

find(3)을 통해 원소 3은 집합 3에 속하는 것을 알 수 있습니다.

이 과정을 거치고 두 원소가 서로소 집합에 속해 있다면

대표 원소가 가리키는 집합을 바꾸는 방법으로 union을 구현할 수 있습니다.

union(2,3)을 한 결과

union연산을 코드로 표현하면

아래와 같습니다.

a는 2, b는 3이라고 했을 때

A는 find(2,arr)을 통해 1이 되고

B는 find(3,arr)을 통해 3이 됩니다.

이때 A와 B가 같다면 서로소 집합이 아니므로 union을 할 필요가 없습니다.

하지만 A와 B가 다르다면

원소 2와 원소 3이 속한 집합이 다르다는 이야기가 되므로

union을 할 수 있습니다.

이때 arr[A]=B를 하게 되면

결과적으로 arr[1]=3이 되어 원소 1이 가리키는 집합은 3이 되고

원소 2는 원소 1을 가리키는 상황이 됨으로써

추후에 find(2)를 하게 되면 결과 값은 3으로

원소 2는 집합 3에 속하게 되는 결과를 얻게 됩니다.

문제점

앞서 union과 find 연산을 구현하였는데

위와 같은 방법으로 union을 많이 하게 되면

발생하는 한 가지 문제가 있습니다.

바로 원소가 자신이 속하는 집합을

알아내기 위해서는 find를 recursive 하게 호출을 하게 되고

원소가 많아지고 union을 많이 할수록 find연산을 호출하는 빈도가 상승하는 문제점이 있습니다.

예를 들어 지금 상황에서 find(4)는 1번의 호출로 원소 4가 집합 4에 속한 것을 알 수 있습니다.

하지만 원소 3이 속한 집합을 알기 위해서는 find(3)을 호출하고 find(3)은 내부에서 다시 find(4)를 호출하게 됩니다.

또한 원소 2가 속한 집합을 알기 위해서는 find(2)를 호출하고 find(2)는 내부에서 다시 find(1)을 호출하고

find(1)은 내부에서 다시 find(3)을 호출하고 find(3)은 다시 find(4)를 호출하게 됩니다.

지금의 예시는 rank가 그렇게 크지 않지만 꼬리에 꼬리는 무는 상황이 반복되게 되면

x가 속한 집합을 알기 위한 find(x)는 find 연산을 최대 rank 만큼 호출하기 때문에 비효율 적이게 됩니다.

(rank를 반영하지 않은 경우 길어지는 형태가 나올 수 있습니다.)

rank반영 X

이러한 문제점을 해결하기 위한

첫 번째 방법은Rank를 이용한 union입니다.

union을 할 때 rank가 작은 집합을 rank가 큰 집합에 속하게 하는 방법입니다.

이러한 방법을 적용한 union은 rank가 같은 경우에만 rank가 증가하기 때문에 최대 rank는 기존의 방식에 비해

더 작은 rank를 갖게 됩니다.

예를 들어 아래와 같은 상황일 때

원소 2와 원소 3이 속한 집합을 합친다고 가정하면

원소 2가 속한 집합 1은 rank가 2이고

원소 3이 속한 집합 3은 rank가 1로

집합 1의 rank가 집합 3의 rank보다 크기 때문에

집합 3의 대표 원소인 3은 집합 1을 가리키게 하면 아래와 같이 rank가 증가하지 않습니다.

Rank를 이용한 union 구현 코드

두 번째 방법은 Path Compression으로 경로 압축 방법이 있습니다.

이 방법은 각 원소가 속한 집합을 알아내는 find 연산에서

각 원소가 자신이 속한 집합을 바로 가리키게 하는 방법입니다.

구현 방법은 아래와 같이

find 함수에서 find를 다시 호출할 때 원소가 자신이 속한 집합을

직접적으로 가리키게 합니다.

경로 압축이 반영이 안 된 경우

find(2)는 find(1)을 호출하고 find(1)은 find(3)을 호출하게 됩니다.

path compression이 반영 X

경로 압축을 반영하게 되면

find(2)는 find(1)을 호출하고 find(1)은 find(3)을 호출합니다.

find(3)은 3이라는 값을 리턴하고 find(1)은 3이라는 값을 받습니다.

이때 find(1)에서 return 하기 전에 arr[1]=3으로 바뀌게 되며 (하지만 이미 3을 가리키기 때문에 변화 없음)

find(2)는 find(1)을 호출했었고 return 값으로 3을 받기 때문에 arr[2]=3으로 원소 2는 집합 3을 가리키게 됩니다.

경로 압축 반영 O

경로 압축에서 find(x)가 호출되어야지만 원소 x가 자신이 속한 집합을 가리키게 됩니다.

(호출 되기 전에는 안 바뀌기 때문에 이 점도 알고 계셔야 합니다.)

마치며

Union-Find는 여러 알고리즘에서 사용됩니다.

대표적 Graph문제에서 연결이 되었는지 안되었는지를 판단하는데 활용되며

구체적으로 Kruskal 알고리즘에서 간선을 연결할 때 사이클이 형성되는지 안되는지를 판별하는 데 사용되기도 합니다.

(이와 관련해서는 Kruskal 알고리즘에 대해 포스팅할 예정입니다.)

잘못된 내용이 있다면 댓글 남겨주시면 반영하겠습니다.

긴 글 읽어 주셔서 감사합니다.

from http://dino-rudy.tistory.com/42 by ccl(A) rewrite - 2021-09-21 23:27:20