[Algorithm] Union-Find 알고리즘이란? ( with 서로소 집합 자료구조 )

 

 

서로소 집합(Disjoint Sets)이란?

 

공통원소가 없는 두 집합을 의미한다.  이는 그래프(Graph) 구조에서 '연결성' 정보를 제공한다. 

 

 

 

 

 

 

4세대 아이돌 8명이다. 우리는 8명을 그룹별로 구분하여 '연결성'을 자료구조로 남기고 싶다.  이때, 서로소 집합 자료구조를 사용할 수 있다.  8명은 각 팀의 리더에게 소속된다. 리더는 나이가 많은 사람이다. 서로소집합의 자료구조는 각 멤버의 리더정보를 담고 있다. 

 

◎ 서로소집합 자료구조

멤버	사쿠라	카즈하	홍은채	가을	안유진	장원영	키나	새나
리더	사쿠라	카즈하	홍은채	가을	안유진	장원영	키나	새나

 

◎ Union-Find 알고리즘 ( 서로소 집합 구현 )

 

처음에는 각 멤버의 리더는 본인이다. 아직 어떤 연결도 없는 상태이다. 그래프에서 연결은 '간선'이다.

여기서 간선 데이터 하나가 들어왔다.

 

- 간선 : [ 카즈하 - 홍은채 ] 

 

1) 리더 탐색 ( Find )

카즈하의 리더는 카즈하이다. 

홍은채의 리더는 홍은채이다. 

 

2) 리더 합병 ( Union )

 

카즈하 리더가 홍은채 리더보다 나이가 많다.

홍은채의 리더는 카즈하의 리더를 따른다.

 

멤버	사쿠라	카즈하	홍은채	가을	안유진	장원영	키나	새나
리더	사쿠라	카즈하	카즈하	가을	안유진	장원영	키나	새나

 

이해하기 쉽게 예를 들면, 길거리에서 양아치 둘이 시비가 붙었다.

 

1) 리더탐색 (FIND)

양아치A : 마! 니 김철수 행님 아나!? 내가 그 행님 모신다!

양아치B : 마! 니는 이대한 행님 아나!? 내가 그 행님 모신다!

 

2) 리더합병(UNION)

양아치A : 마! 김철수 행님이 이대한 행님보다 나이가 많다!

양아치B : 와.. 그럼 이대한 행님이 김철수 행님 모셔야겠네...

 

이대한은 김철수를 행님으로 모시고 이대한 밑에 있는 양아치B는 자연스레 김철수집단에 소속된다. 

이것이 'Union-Find 알고리즘'이다. 이는 두 단계로 진행된다.

 

1) 리더탐색(Find)

2) 리더합병(Union) 

 

계속 간선을 추가해보자.

 

- 간선 : [ 사쿠라 - 카즈하 ]

 

1) 리더 탐색 ( Find )

사쿠라의 리더는 사쿠라이다.

카즈하의 리더는 카즈하이다. 

 

2) 합치기 ( Union )

 

사쿠라 리더가 카즈하 리더보다 나이가 많다.

카즈하의 리더는 사쿠라의 리더를 따른다.

 

카즈하를 리더로 따르는 홍은채는 자연스레 사쿠라팀에 소속되며

사쿠라-카즈하-홍은채로 이어지는 하나의 그래프가 형성된다.

 

멤버	사쿠라	카즈하	홍은채	가을	안유진	장원영	키나	새나
리더	사쿠라	사쿠라	카즈하	가을	안유진	장원영	키나	새나

 

 

- 간선 : [ 안유진  - 장원영 ]

 

1) 리더 탐색 ( Find )

안유진의 리더는 안유진이다.

장원영의 리더는 장원영이다.

 

2) 리더 합병( Union )

 

안유진 리더가 장원영 리더보다 나이가 많다.

장원영의 리더는 안유진의 리더를 따른다.

 

멤버	사쿠라	카즈하	홍은채	가을	안유진	장원영	키나	새나
리더	사쿠라	사쿠라	카즈하	가을	안유진	안유진	키나	새나

 

이 과정을 반복하면 아래와 같은 테이블이 만들어 진다.

 

◎ 서로소집합 자료구조

멤버	사쿠라	카즈하	홍은채	가을	안유진	장원영	키나	새나
리더	사쿠라	사쿠라	카즈하	가을	가을	안유진	키나	키나

 

 

Union-Find 알고리즘으로 만들어진 서로소집합 자료구조는 '연결성' 정보를 가진다.

 

사쿠라와 카즈하는 같은 리더를 가지므로 연결되어 있고

가을과 홍은채는 리더가 서로 다르므로 연결되어 있지 않다. 

 

 

 

 

 

르세라핌이냐 아이브이냐 피프티피프티이냐를 구분하는 기준은 '리더' 즉, 루트(ROOT)이다.

 

르세라핌 : 홍은채 ➠ 카즈하 ➠ 사쿠라(리더,root)

아이브 : 장원영 ➠ 안유진 ➠가을(리더,root)

 

그럼 르세라핌과 아이브를 하나로 합쳐보자 ( UNION )

 

 

- 간선 : [ 홍은채 - 안유진 ] 

 

1) 리더 탐색(Find)

홍은채 ➠ 카즈하 ➠ 사쿠라(리더,root)

안유진 ➠가을(리더,root)

 

2) 리더 합병(Union)

 

사쿠라가 가을보다 나이가 많으므로

가을은 사쿠라를 리더로 따른다. (가을 ➠ 사쿠라)

 

멤버	사쿠라	카즈하	홍은채	가을	안유진	장원영	키나	새나
리더	사쿠라	사쿠라	카즈하	사쿠라	가을	안유진	키나	키나

 

홍은채와 장원영이 연결되어 있는지 확인해보자.

 

홍은채 ➠ 카즈하 ➠ 사쿠라(리더) 

장원영 ➠ 안유진 ➠ 가을 ➠ 사쿠라(리더)

 

홍은채와 장원영은 같은 리더를 따르므로 둘은 연결되어있다. 

이와 같이, 서로소 집합 자료구조는 그래프의 '연결성' 정보를 가지고 있기에 다양한 알고리즘에서 사용된다. 

 

 

그럼 이를 구현해보자. 

( 참고로, 리더는 노드의 root를 의미하며 root는 값이 작은 노드가 루트가 되는 것이 일반적이다. )

 

코드 ( python )

# 루트 탐색 ( Find )
def find_root(parent,x) :
  if parent[x] != x : return find_root(parent,parent[x])
  else : return x

# 간선 합치기 ( Union )
def union_graph(parent,a,b) :

  a_root = find_root(parent,a)
  b_root = find_root(parent,b)
  # 값이 작으면 루트
  if a_root > b_root : parent[a_root] = b_root
  else : parent[b_root] = a_root


n,e = map(int,input().split()) #노드의 개수 : n , 간선의 개수 : e
parent = [0] * (n+1) # 서로소 집합 테이블

# 서로소 집합 테이블 초기화
for i in range(1,n+1) :
  parent[i] = i

# Union-Find 알고리즘 시작
for _ in range(e) :
  a,b = map(int,input().split()) #간선 입력받기
  union_graph(parent,a,b) # 간선 합치기 


# 루트 노드 출력
print("각 노드의 루트노드 출력 :  ",end=' ')
for i in range(1,n+1) :
  print(find_root(parent,i),end=' ')

print()

# 부모 노드 출력
print("각 노드의 부모노드 출력 :  ",end=' ')
for i in range(1,n+1) :
  print(parent[i],end=' ')

 

- 입력

6 4
1 4
2 3
2 4
5 6

 

- 출력

각 노드의 루트노드 출력 :   1 1 1 1 5 5 
각 노드의 부모노드 출력 :   1 1 2 1 5 5

 

 

루트노드 탐색은 재귀호출로 구현하였다. 

 

위 코드는 한가지 아쉬운 점이 있다. 

 

노드	사쿠라	카즈하	홍은채	가을	안유진	장원영	키나	새나
부모	사쿠라	사쿠라	카즈하	가을	가을	안유진	키나	키나

 

만약 [ 홍은채 - 김채원 ] 관계가 새로 들어왔다고 가정하자.

 

홍은채는 리더를 탐색하기 위해,

홍은채 ➠ 카즈하 ➠ 사쿠라 순으로 재귀호출한다. 노드의 개수가 V개라면 최대 O(V)의 시간복잡도를 가질 수 있다. 

 

이는 비효율이다.

만약 홍은채가 카즈하(부모)가 아니라 바로 사쿠라(리더,루트)를 본다면 호출횟수를 줄일 수 있다.

 

Find 메소드를 수정해보자.

# 루트 탐색 ( Find )
def find_root(parent,x) :
  if parent[x] != x : parent[x]=find_root(parent,parent[x]) # 부모를 루트로 초기화
  return parent[x]

 

홍은채 ➠ 카즈하 ➠ 사쿠라 로 재귀호출이 되고 함수가 종료되면서 return 값으로 루트를 반환하면

카즈하, 홍은채가 부모를 루트로 변환한다.  

 

노드	사쿠라	카즈하	홍은채	가을	안유진	장원영	키나	새나
부모	사쿠라	사쿠라	사쿠라	가을	가을	가을	키나	키나

 

- 입력

6 4
1 4
2 3
2 4
5 6

 

- 출력

각 노드의 루트노드 출력 :   1 1 1 1 5 5 
각 노드의 부모노드 출력 :   1 1 1 1 5 5

 

 

그럼 이제 [ 홍은채 - 김채원 ] 간선이 추가되어도 홍은채 ➠ 카즈하 ➠ 사쿠라 가 아니라 홍은채 ➠ 사쿠라로 경로압축이 된다. 이와 같이, Union-Find 알고리즘을 개선할 수 있다.

 

---

 

참고자료 

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서