그래프 이론 - Union Find 알고리즘

Jaegil Jeong·2022년 9월 16일

알고리즘

목록 보기

4/6

1. Disjoint Set (서로소 집합)

수학에서 서로소란 아래와 같이 공통 원소가 없는 두 집합을 의미한다.

A: {1, 3, 5} B:{2, 4, 6}

알고리즘에서 서로소 집합은 서로소 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조이다.
서로소 집합 자료구조는 Union합집합, Find찾기 두개의 연산으로 처리할 수 있다.

Union: 두 개의 원소가 주어졌을 때, 각 원소가 포함되는 두 집합을 하나로 합치는 연산

Find: 특정 원소가 어느 집합에 포함되는지 찾는 연산

즉, Union 연산을 통해 공통 원소가 있는 두 집합을 중복 없는 하나의 집합으로 만들 수 있고 Find 연산으로 두 원소가 같은 집합에 있는지 또는 서로소 집합에 있는지 확인할 수 있다.

2. Union (합집합 연산)

서로소 집합 자료구조를 구현하기 위해서 트리 자료구조를 이용하여 집합을 표현하는데, 서로소 집합의 정보가 주어졌을 때 (Uion) 서로소 계산 알고리즘은 다음과 같은 과정으로 진행된다.

Uinon 연산을 확인하여 , 서로 연결된 두 노드 A, B를 확인한다.
1) A와 B의 루트 노드 A', B'를 각각 찾는다. (A' < B')
2) A'를 B'의 부모 노드로 설정한다. (B'가 A'를 가리키도록 한다.)

모든 Uion 연산을 처리할 때까지 1 번 과정을 반복한다.

예시를 들어보면, 전체 집합이 {1, 2, 3, 4, 5, 6} 6개의 원소로 구성될 때 아래와 같은 부분집합 정보 즉, Uion 연산 정보가 주어진다고 가정해보자.

union (1, 4)
union (2, 3)
union (2, 4)
union (5, 6)

위와 같은 연산은 1, 4가 같은 집합, 2, 3이 같은 집합, 2, 4가 같은 집합, 5, 6이 같은 집합임을 나타낸다.

이렇게 모든 Union 연산을 수행한 후에 결과적으로 어떤 형태의 부분 집합으로 나타날지 확인할 수 있다.
차례대로 알고리즘을 수행하보자.
먼저 부모 테이블을 각각 자기 자신으로 초기화 한다.

노드	1	2	3	4	5	6
부모노드	1	2	3	4	5	6

Uion(1, 4) , 1번 과정에 따라 두 노드의 루트 노드를 찾아야 한다.

루트 노드는 말그대로 뿌리가 되는 노드이다.
현재 노드의 부모 노드, 부모 노드의 부모 노드, 이런 식으로 거슬러 올라 갔을 때 결국 자기 자신이 부모노드인 노드에 도달하게 되는데 이렇게 도달한 마지막 노드를 루트 노드라고 한다.

위 테이블과 같이 처음 초기화 한 시점에서는 연결된 노드 없이 모든 노드가 하나의 루트인 상태이다.
즉, 아직 연결된 노드가 없는 초기 상태에서 1번, 4번 노드의 루트 노드는 자기 자신인 셈이다.

이제 알고리즘 2번 과정을 수행한다.
두 루트 노드 A', B' 중 작은 노드가 큰 노드의 부모 노드가 된다. 여기서는 1이 4의 부모 노드가 되므로 4가 1을 가리킨다고 할 수 있다. 그래프로 표현하면 아래와 같고 부모 테이블도 업데이트 해주자.

노드	1	2	3	4	5	6
부모노드	1	2	3	1	5	6

이로서 1과 4는 같은 집합에 속하게 되었다.

그 다음 Union(2, 3) 연산도 동일하다.
두 노드 모두 자기 자신을 부모 노드로 가지며 숫자가 작은 2가 3의 부모 노드가 되어 아래와 같이 표현된다.

노드	1	2	3	4	5	6
부모노드	1	2	2	1	5	6

다음으로 Union(2, 4) 연산이다.
처음으로 자기 자신이 부모가 아닌 노드가 나왔다.
먼저 두 노드의 부모 노드는 각각 2, 1이다. 이 경우 2의 부모 노드가 1로 갱신되며 아래와 같이 표현된다.

노드	1	2	3	4	5	6
부모노드	1	1	2	1	5	6

마지막으로 Union(5, 6)이다.
두 노드 모두 자기 자신을 부모 노드로 가지며 5가 6의 부모 노드가 되어 아래와 같이 표현된다.

노드	1	2	3	4	5	6
부모노드	1	1	2	1	5	5

이렇게 모든 유니온 연산을 수행했다. 그래프를 직관적으로 봤을 때 {1, 2, 3, 4}와 {5, 6} 두 개의 집합으로 구분되는 것을 알 수 있다.

3. Find (찾기 연산)

Union 연산에서 주의할 점은 연산할 두 노드의 부모 노드가 아닌 루트 노드를 찾기 위해 부모 테이블을 재귀적으로 거슬러 올라가야 한다는 것이다. 이를 위해 부모 테이블을 항상 가지고 있어야한다.

노드	1	2	3	4	5	6
부모노드	1	1	2	1	5	5

예를 들어, 위 테이블에서 노드 3의 부모는 노드 2이다. 노드 2의 부모는 노드 1이며 노드 1의 부모는 자기 자신이므로 노드 3의 루트 노드가 노드 1인 것이다.

즉, 서로소 집합 알고리즘을 통해 루트 노드를 찾으려면 재귀적으로 부모 테이블을 거슬러 올라가야 한다는 점을 기억하자. Find찾기는 이러한 연산 과정을 의미한다.

Find 연산을 통해 우리는 해당 원소가 어떤 집합에 속하는 지 알 수 있다.
그래프를 통해 이야기 하면, 두 원소의 Find 연산 결과가 같다는 것은 (같은 루트 노드를 갖는 다는 것은) 두 노드가 연결되어 있음을 의미한다.

Union & Find 소스코드는 다음과 같다.

## 서로소 집합 알고리즘

#특정 원소의 루트 노드 찾기 ( 어떤 집합에 속하는 지 찾기)
def find_parent(parent, x):
  if parent[x] != x: #루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀 호출
	  return find_parent(parent, parent[x])

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
  a = find_parent(parent, a) # a의 루트 노드 찾기
  b = find_parent(parent, b) # b의 루트 노드 찾기
  if a > b:  #작은 루트 노드를 큰 루트 노드의 부모 노드로 설정 
    parent[a] = b
  else:
    parent[b] = a 

#노드와 간선 개수 입력 
v, e  = map(int, input().split()) 

# 부모 테이블 초기화
parent = [0] * (v+1) 
for i in range(1, v+1):
  parent[i] = i

#노드 연결 정보를 입력 받아 Union 연산
for i in range(e):
  a, b = map(int, input().split())
  union_parent(parent, a, b)

# 각 노드의 루트 노드 출력 (어떤 집합에 속해 있는지)
print('각 원소가 속한 집합: ', end = ' ')
for i in range(1, v+1):
  print(find_parent(parent, i))

print()

print('부모 테이블: ', end= ' ')
for i in range(1, v+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

출력 결과를 보면 위에서 그래프와 테이블로 봤던 결과와 동일하다.
루트 노드의 출력 결과를 보면 {1, 2, 3, 4}가 같은 루트 노드를 갖고, {5, 6}이 같은 루트 노드를 가지므로 두 개의 부분 집합이 형성된 것을 알 수 있다.

다만, 위와 같은 방식은 Find 연산으로 루트 노드를 찾을 때 비효율 적인 부분이 있다.
예를 들어 전체 집합이 {1, 2, 3, 4, 5} 일때 모든 원소가 연결되어 있다고 가정하면 다음과 같이 나타낼 수 있다.

노드	1	2	3	4	5
부모노드	1	1	2	3	4

이 경우, 노드 5의 루트를 찾기 위해서는 5 -> 4 -> 3 -> 2 -> 1 의 과정으로 부모 테이블을 모두 탐색해야 한다. 즉, 최악의 경우 시간 복잡도가 O(V)가 된다.

결과적으로 해당 코드에서는 Find 또는 Uinon 연산이 M 번 수행되면 O(VM)의 시간 복잡도를 갖게 되어 비효율적이다.

그러나 Find 함수를 간단한 방법으로 최적화 시킬 수 있다. 바로 경로 압축Path Compression 기법이다.
아래와 같이 경로 압축은 find 함수를 재귀적으로 호출한 후 부모 테이블 값을 갱신한다.

def find_parent(parent, x):
	if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]

재귀 호출 뒤 루트 노드만 반환하는 것이 아니라, 부모 테이블을 갱신한 뒤 해당 루트 노드를 반환하게 되면 부모 테이블에 자신의 루트 노드를 갖게되어 루트 노드로 바로 접근 가능하다.
이전 예시와 동일하게 전체 집합이 {1, 2, 3, 4, 5}이고 모든 원소가 연결되어 있는 상황을 보자.

Union 연산이 (4, 5), (3, 4), (2, 3), (1, 2)와 같이 주어졌다고 했을 때,
최종적으로 그래프는 아래와 같이 표현된다.

노드	1	2	3	4	5
부모노드	1	1	1	1	1

이렇게 모든 원소의 부모 테이블 값을 루트 노드로 만들어 두면 이후 Find 연산 시 바로 루트 노드를 찾을 수 있어 시간 복잡도를 개선시킬 수 있다.

노드의 개수가 V개이고 최대 V-1개의 Union 연산과 M개의 Find 연산이 가능할 때, 경로 압축 방법을 적용한 시간 복잡도는 O(V + M(1+log2-M/VV))로 알려져 있다.

이는 노드 개수가 1,000개, Union과 Find연산이 총 100만 번 수행된다고 했을 때 V + log2V를 계산하여 약 1,000만 번 정도의 연산이 필요한 것으로 이해하면 된다.

경로 압축법을 사용한 서로소 집합 알고리즘 소스코드는 다음과 같다.

## 서로소 집합 알고리즘

#특정 원소의 루트 노드 찾기 ( 어떤 집합에 속하는 지 찾기)
def find_parent(parent, x):
  if parent[x] != x: #루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀 호출
	  parent[x] = find_parent(parent, parent[x] 재귀 호출 후 부모 노드 갱신
  return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
  a = find_parent(parent, a) # a의 루트 노드 찾기
  b = find_parent(parent, b) # b의 루트 노드 찾기
  if a > b:  #작은 루트 노드를 큰 루트 노드의 부모 노드로 설정 
    parent[a] = b
  else:
    parent[b] = a 

#노드와 간선 개수 입력 
v, e  = map(int, input().split()) 

# 부모 테이블 초기화
parent = [0] * (v+1) 
for i in range(1, v+1):
  parent[i] = i

#노드 연결 정보를 입력 받아 Union 연산
for i in range(e):
  a, b = map(int, input().split())
  union_parent(parent, a, b)

# 각 노드의 루트 노드 출력 (어떤 집합에 속해 있는지)
print('각 원소가 속한 집합: ', end = ' ')
for i in range(1, v+1):
  print(find_parent(parent, i))

print()

print('부모 테이블: ', end= ' ')
for i in range(1, v+1):
	print(parent[i], end = ' ')