[Algorithm & DS] 그래프 - 서로소 집합 자료구조

leehyuna·2022년 6월 19일
data structure
1

Algorithm & DS

목록 보기
4/6

✅ 서로소 집합

✏️ 서로소 집합

  • 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미한다.

✏️ 서로소 집합 자료구조

  • 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
  • 서로소 집합 자료구조는 두 종류의 연산을 지원한다.
    • 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
    • 찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
  • 서로소 집합 자료구조는 합치기 찾기(Union-Find) 자료구조라고 불리기도 한다.

서로소 집합 자료구조를 표시할 때는 기본적으로 트리 자료구조를 이용한다. 트리 자료구조는 계층을 갖고 있다. 즉, 노드들 간의 부모-자식 관계가 있음을 가정한다.

  • 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정을 다음과 같다.
    1. 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다.
    • 1) A와 B의 루트 노드 A',B'을 각각 찾는다.
    • 2) A'을 B'의 부모 노드로 설정한다.
    1. 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복한다.

🤓 서로소 집합 자료구조 : 동작 과정 살펴보기

1. 첫 번째 초기 단계
초기 단계에서 해야 할 가장 중요한 일은 노드의 개수만큼의 부모 테이블을 초기화 하는 것이다. 예를 들어, 노드의 개수가 N개 일 때, N+1 길이의 1차원 리스트를 초기화한다. 이 때, 리스트의 원소값은 해당 인덱스값을 넣어준다. 즉, 처음에는 모든 원소가 자기 자신을 부모로 가지도록 설정한다. 초기단계로 다음과 같은 데이터가 주어졌다.

2. 두 번째 단계 - union 첫 번째 연산 수행
union 첫 번째 연산으로 (1, 4)가 들어왔다. 앞에서 공부한 Union 연산을 수행하며 다음과 같이 부모 테이블의 값을 업데이트 해준다.

위 처럼 Union 연산 정보에 의해 4번 노드의 부모 노드는 1번 노드라는 것을 알게 되었다. 따라서 위와 같이 부모테이블의 4번 인덱스 값을 4 -> 1로 업데이트 한다.

3. 세 번째 단계 - union 두 번째 연산 수행

이번에 주어진 Union 연산 정보에 의해 3번 노드의 부모 노드는 2번 노드이다. 따라서 위와 같이 부모 테이블의 3번 인덱스 값이 2번으로 업데이트 된다.

4. 네 번째 단계 - union 세 번째 연산 수행

여기서 헷갈리지 말아야 한다. 주어진 Union 연산 정보는 (2, 4) 이다. 즉 부모 테이블 상에서 4번 노드의 부모 노드(부모 테이블 값)는 1이다. 반면, 2번 노드의 부모 노드(부모 테이블 값)는 2이다. 따라서 4번 노드의 부모 노드 값이 1로 더 작으므로 2번 노드의 부모노드 값인 2는 1로 업데이트 해야 한다. 그래서 자료구조 그림 상으로는 2 -> 1번 노드로 가는 간선이 생겨난다.

5. 다섯 번째 단계 - union 네 번째 연산 수행

이번에 주어진 연산 정보에 의해 6번 노드의 부모 테이블 값은 5로 업데이트 된다. 그리고 모든 Union 연산을 수행했으니 알고리즘이 종료되고 다음과 같이 최종 부모 테이블이 완성된다.

📌 위 부모 테이블을 해석하게 되면 6번 노드의 부모노드는 5번이고 5번의 부모노드는 5번으로 결국 하나의 서로소 집합으로 구성된다. 반면에 1,2,4번의 부모노드는 1이고 3번 노드의 부모노드는 2번 노드이지만 2번 노드의 부모노드는 재귀적으로 또 1번 노드이므로 결국 최종 루트 노드가 1번 노드로 또 하나의 서로소 집합으로 구성된다.

🤓 서로소 집합 자료구조 : 연결성

  • 위 설명과 같이, 서로소 집합 자료구조에서는 연결성을 통해 손쉽게 집합의 형태를 확인할 수 있다.

  • 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없다.

    • 루트 노드를 찾기 위해서는 부모 테이블을 계속해서 확인하며 거슬러 올라가야 한다.

  • 다음 예시에서 노드 3의 루트를 찾기 위해서는 노드 2를 거쳐 노드 1에 접근해야 한다.

✏️ 서로소 집합 자료구조 : 기본적인 구현 (Python)

import sys

v, e = map(int, input().split())
parent = [0] * (v+1)
for i in range(1, v+1) :
    parent[i] = i
    
# find 연산
def find_parent(parent, x) :
    # 부모노드와 자식노드가 같지 않다면, 부모노드가 따로 있다는 의미
    if parent[x] != x :
        return find_parent(parent, parent[x]) # 그 부모노드를 자식으로 하는 또 다른 부모노드를 재귀적으로 탐색
    
    return x # 부모노드 == 자식 노드 -> 해당 노드 리턴

def union_parent(parent, a, b) :
    # a, b 각 부모노드 탐색 - Find 연산
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    
    if a < b :
        parent[b] = a
    else :
        parent[a] = b
        

for _ in range(e) :
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소의 루트 노드 출력
print('# 각 원소의 루트 노드들 : ', end='')
for i in range(1, v+1) :
    root = find_parent(parent, i)
    print(root, end=' ')
print()
# 부모 테이블 출력 (직계 부모노드를 의미)
print('# 각 원소의 직계 부모 노드들 : ', end='')
for i in range(1, v+1) :
    print(parent[i], end=' ')

🤓 서로소 집합 자료구조 : 기본적인 구현 방법의 문제점

  • 합집합(Union) 연산이 편향되게 이루어지는 경우 찾기(Find) 함수가 비효율적으로 동작한다.
  • 최악의 경우에는 찾기(Find) 함수가 모든 노드를 다 확인하게 되어 시간복잡도가 O(V)가 된다.
    • 다음과 같이 {1,2,3,4,5}의 총 5개의 원소가 존재하는 상황을 확인해보자.

🤓 서로소 집합 자료구조 : 경로 압축

  • 찾기(Find) 함수를 최적화하기 위한 방법으로 경로 압축(Path Compression)을 이용할 수 있다.
    • 찾기(Find) 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신한다.
import sys

v, e = map(int, input().split())
parent = [0] * (v+1)
for i in range(1, v+1):
    parent[i] = i

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

for _ in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

print('# 각 원소의 루트노드 출력:', end='')
for i in range(1, v+1):
    root = find_parent(parent, i)
    print(root, end=' ')
print()
print('# 위 find 연산 후 업데이트된 부모 테이블 출력:', end='')
for i in range(1, v+1):
    print(parent[i], end=' ')
  • 경로 압축 기법을 적용하면 각 노드에 대하여 찾기(Find) 함수를 호출한 이후에 해당 노드의 루트 노드가 바로 부모 노드가 된다.
  • 동일한 예시에 대해서 모든 합집합(Union) 함수를 처리한 후 각 원소에 대하여 찾기(Find) 함수를 수행하면 다음과 같이 부모 테이블이 갱신된다.
  • 기본적인 방법에 비하여 시간복잡도가 개선된다.

✏️ 서로소 집합을 활용한 사이클 판별

  • 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.
    • (참고 : 유방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있다.)
  • 사이클 판별 알고리즘은 다음과 같다.
    1. 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다. (Find)
    • 1) 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행한다.
    • 2) 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.
    1. 그래프에 포함되어 있는 모든 간선에 대해 1번 과정을 반복한다.

🤓 서로소 집합을 활용한 사이클 판별 : 동작 과정 살펴보기

1. 초기 단계
모든 노드에 대하여 자기 자신을 부모로 설정하는 형태로 부모 테이블을 초기화 한다.

2. Step 1
간선 (1,2)을 확인한다. 노드 1과 노드 2의 루트 노드는 각각 1과 2 이다. 따라서 더 큰 번호에 해당하는 노드 2의 부모노드를 1로 변경한다.

3. Step 2
간선 (1,3)을 확인한다. 노드 1과 노드 3의 루트 노드는 각각 1과 3 이다. 따라서 더 큰 번호에 해당하는 노드 3의 부모노드를 1로 변경한다.

4. Step 3
간선 (2,3)을 확인한다. 이미 노드 2와 노드 3의 루트 노드는 모두 1이다. 다시 말해 사이클이 발생한다는 것을 알 수 있다.

🤓 서로소 집합을 활용한 사이클 판별 : python 구현

import sys

v, e = map(int, input().split())
parent = [0] * (v+1)
for i in range(1, v+1) :
    parent[i] = i
    
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
        
cycle = False
for _ in range(e) :
    a, b = map(int, input().split())
    if find_parent(parent, a) == find_parent(parent, b) :
        cycle = True
        break
    else :
        union_parent(parent, a, b)
        
if cycle :
    print('사이클이 존재합니다.')
else :
    print('사이클이 존재하지 않습니다.')

[ 참고 자료 ]
1. https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8
2. https://techblog-history-younghunjo1.tistory.com/257?category=1014800

profile
이전 포스트

[Algorithm & DS] 최소 신장 트리 (MST, Minimum Spanning Tree)

다음 포스트

[Algorithm & DS] 그래프 - Kruskal 알고리즘

0개의 댓글