[알고리즘] 서로소 집합 알고리즘 (Union-Find)

서로소 집합 (Disjoint Sets)

 

서로소 집합은 공통 원소가 없는 두 집합을 의미한다. A = {1, 2} 와 B = {3, 4} 가 있다면 두 집합은 서로소 관계이다.

서로소 집합 자료구조란 서로소 부분들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조다. 서로소인지 판별하려면 union과 find 연산이 필요하다. union연산은 두 집합을 하나의 집합으로 합치는 연산이고 find 연산은 어떤 원소가 주어졌을 때 이 원소가 속한 집합의 대표를 찾는 연산이다. 즉 find 를 통해 주어진 두 집합의 대표를 비교하여 서로 서로소인지 확인이 가능 한 것이다.

때문에 서로소 집합 자료구조는 유니온파인드(Union-Find)라고도 불리운다.

 

집합 {1, 2, 3, 4, 5, 6}이 있고 여기에 union(1, 4), union(2, 3), union(2, 4), union(5, 6) 연산을 해보겠다.

 

우선 초기에는 각각의 원소의 대표는 자기 자신이다. 

 

0. 초기

 

 

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

 

 

1. union(1, 4)

노드 번호	1	2	3	4	5	6
부모 =	1	2	3	1	5	6

 

원소의 번호가 작은 것을 대표로 두는 것이, 즉 부모 노드로 두는 것이 일반적인 구현 방식이다. 때문에 4의 부모 노드를 4에서 1로 변경하였다. 1과 4는 서로소였다가 이제 합쳐진 것이다.

 

2. union(2, 3)

 

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

이번에도 역시 3번의 부모 노드를 2번의 부모 노드로 변경해주었다.

 

3. union(2, 4)

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

2와 4를 합치기 위해 부모 원소를 비교한다. 2의 부모는 2이고 4의 부모는 1이다. 1이 더 작기 때문에 2의 부모를 1로 변경한다.

 

4. union(5, 6)

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

5와 6을 합친다. 6의 부모를 더 작은 5로 변경한다!

 

 

이렇게 그림으로 진행한 과정을 코드로 구현하면 다음과 같다.

 

 

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x
 
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
 
# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
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), end=' ')
 
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 5 5
부모 테이블: 1 1 2 1 5 5

 

3번 노드를 보면 부모는 2이지만 3이 속한 집합의 대표는 1이라고 볼 수 있다.

 

이 문제를 더 확대해서 살펴보면 다음과 같다.

 

{1, 2, 3, 4, 5}에 대해서 (4,5), (3,4), (2,3), (1,2) 이렇게 총 4개의 union 연산을 하면 아래의 그림처럼 그려진다. 5번 노드의 대표를 찾기 위해서는 4번 노드 갔다가 3번 노드 가고 2번 노드가고 1번 노드 까지 가야 자신의 대표 노드가 1번인줄 안다.

이렇게 재귀적으로 탐색해서 찾아가면 노드의 개수가 V개이고 연산의 개수가 M개일 때, 전체 시간 복잡도는 O(VM)이 되어 비효율적이다.

 

이런 문제를 해결하기 위해 find 연산에서 바로 집합의 대표를 찾을 수 있게 최적화한 것이 경로 압축이다. 경로 압축에서는 find 함수를 재귀적으로 호출한 뒤 부모 테이블값을 갱신하는 기법이다.

 

 

# 특정 원소가 속한 집합을 찾기
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)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
 
# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
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), end=' ')
 
print()
 
# 부모 테이블 내용 출력하기
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

 

그림으로 시각화하면 다음과 같다.

 

 

시간 복잡도

경로 압축을 사용한 서로소 알고리즘의 시간 복잡도는 $ O(V+M(1+log_{2-M/V}V)) $ 이다. 

 

 

사이클 판별

서로소 집합을 사용하여 무방향 그래프에서 사이클을 판별할 수 있다. 번외로 방향 그래프에서의 사이클 여부는 DFS를 사용하여 판별할 수 있고, 음의 간선이 있는 그래프에서는 벨만 포드를 사용하여 판별할 수 있다.

 

사이클 판별은 수행은 다음과 같다.

 

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.

    - 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.

    - 루트 노드가 서로 같다면 사이클이 발생한 것이다.

 

2. 그래프 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.

 

위와 같이 무방향 그래프를 살펴보자.

 

초기는 각자를 자기 부모로 삼는다.

인덱스	1	2	3
부모	1	2	3

 

 

1과 2를 잇는 간선을 확인한다. 1과 2의 부모를 비교후 2의 부모가 더 크니 1로 변경한다.

 

인덱스	1	2	3
부모	1	1	3

 

(1,3) 간선을 확인후 3의 부모를 변경한다.

인덱스	1	2	3
부모	1	1	1

 

모든 원소의 부모는 1이 되었다.

이제 (2, 3)을 확인해보면 둘다 1을 부모노드로 갖고 있는 것을 확인 할 수 있다. 때문에 사이클이 발생한다는 것을 알 수 있다.

 

 

# 특정 원소가 속한 집합을 찾기
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)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
 
# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기
 
# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i
 
cycle = False # 사이클 발생 여부
 
for i in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    # 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
    else:
        union_parent(parent, a, b)
 
if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")

 

입력

3 3
1 2
1 3
2 3

 

출력

사이클이 발생했습니다.