이코테 강의를 통해서 공부했습니다!

서로소 집합 자료구조 (Union-Find)

서로소 집합 자료구조는 알고리즘이 아니라 자료구조로 분류된다. 서로소 집합 자료구조의 union과 find 연산이 사이클 판별 알고리즘에서 이용되기 때문에 사이클 판별을 하기 위해 서로소 집합 자료구조를 먼저 공부해야한다!

• 서로소 집합 (Disjoing Sets) : 공통 원소가 없는 두 집합
• 서로소 집합 자료구조
  • 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
  • 데이터들의 집합 관계를 표현하는 자료구조
  • 트리 활용
• 서로소 집합 자료구조의 연산
  • 합집합 (Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
    • Union(A, B) : 원소 A가 속한 집합과 원소 B가 속한 집합을 합집합시킨다.
  • 찾기 (Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
• 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리기도 함

서로소 집합의 union 연산 동작 설명

1. 합집합 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
   1. A와 B의 루트 노드 A’, B’를 각각 찾는다.
   2. A’을 B’의 부모 노드로 설정한다.
2. 모든 합집합 연산을 처리할 때까지 1번의 과정을 반복한다.

서로소 집합 자료구조의 세부 동작 과정

• 초기 단계에서는 원소 각각을 집합으로 취급하고, 각 노드의 부모는 자기 자신으로 설정한다.
• 합치기 연산을 할 때는 일반적으로 두 노드 중 작은 번호의 노드를 루트 노드로 설정한다. → 큰 노드가 작은 노드를 가리키도록 한다.
• (집합)같은 집합으로 연결된 노드 == (그래프)루트 노드가 같은 노드
  • (그래프)루트 노드 == (테이블)자기 자신을 부모로 설정한 노드
• 서로소 집합 자료구조에서는 연결성을 통해 손쉽게 집합의 형태를 확인할 수 있다.
  • 하나의 루트노드를 가지고 하나의 트리형태로 구성된 그래프는 같은 집합이라고 표현할 수 있다.
• 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없다.
  • 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야 한다.

1. Union 연산을 집합으로 표현하기 : 우리가 중고등학교 때 배우는 합집합
2. Union 연산을 트리로 표현하기 : 컴퓨터과학의 관점에서 표현한 합집합
   
3. Union 연산을 테이블로 표현하기 : 코드 구현을 용이하게 하는 표현
   

서로소 집합 자료구조의 구현

기본적인 구현 방법 (Python)

# 서로소 집합 자료구조 : 기본적인 구현 방법

# 연산 1 : 특정 원소가 속한 집합(루트 노드)를 찾아주는 연산 (find)
def find_parent(parent, x):
    # 루트 노드를 찾을 때까지 재귀 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x

# 연산 2 : 두 원소가 속한 집합을 합치는 연산 (union)
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

# 입력
num_node, num_edge = map(int, input().split())
parent_table = [0] * (num_node + 1)

# 부모 테이블 초기화
for i in range(1, num_node + 1):
    parent_table[i] = i;

# Union 연산을 입력받아 수행
for i in range(num_edge):
    a, b = map(int, input().split())
    union_parent(parent_table, a, b)

# 출력
print('각 원소가 속한 집합: ', end="")
for i in range(1, num_node + 1):
    print(find_parent(parent_table, i), end=' ')

print()

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

'''
입력
6 4
1 4
2 3
2 4
5 6
'''
'''
출력
각 원소가 속한 집합 : 1 1 1 1 5 5
부모 테이블 : 1 1 2 1 5 5
'''

기본적인 구현 방법의 문제점

• 합집합 연산이 편향되게 이루어지는 경우 찾기(Find) 함수가 비효율적으로 동작한다.
• 최악의 경우 찾기 함수가 모든 노드를 다 확인하게 되어 시간 복잡도가 O(V)가 되버린다.

문제 해결 : 경로 압축

• 찾기 함수를 최적화하기 위한 방법으로 경로 압축(Path Compression)을 이용할 수 있다.
• 경로 압축 : 찾기 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신한다.
• find 연산을 호출한 뒤에는 부모 테이블의 값을 루트로 변경해 줌!

1. find_parent : basic

   def find_parent(parent, x):
       # x가 루트 노드가 아니라면
       if parent[x] != x:
   				# x의 루트 노드를 찾아서 return
           return find_parent(parent, parent[x])
   		# x가 루트 노드라면 바로 return
       return x

2. find_parent : with path compression

   def find_parent(parent, x):
   		# x가 루트 노드가 아니라면
       if parent[x] != x:
   				# x의 루트 노드를 찾아서 parent 값으로 저장해주고 return
           parent[x] = find_parent(parent, parent[x])
   		# x가 루트 노드라면 바로 return
       return parent[x]

3. find_parent : with 긍정 조건문

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

경로 압축을 이용한 구현 (Python)

# 서로소 집합 자료구조 : 기본적인 구현 방법

# 연산 1 : 특정 원소가 속한 집합(루트 노드)를 찾아주는 연산 (find)
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 연산 2 : 두 원소가 속한 집합을 합치는 연산 (union)
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

# 입력
num_node, num_edge = map(int, input().split())
parent_table = [0] * (num_node + 1)

# 부모 테이블 초기화
for i in range(1, num_node + 1):
    parent_table[i] = i;

# Union 연산을 입력받아 수행
for i in range(num_edge):
    a, b = map(int, input().split())
    union_parent(parent_table, a, b)

# 출력
print('각 원소가 속한 집합: ', end="")
for i in range(1, num_node + 1):
    print(find_parent(parent_table, i), end=' ')

print()

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

서로소 집합을 활용한 사이클 판별 알고리즘

• 서로소 집합 자료구조의 사용 → 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.
  • 참고) 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있다.
• 사이클 판별 알고리즘
  1. 각 간선의 정보를 하나씩 확인하며 간선에 연결된 두 노드의 루트 노드를 확인한다.
     a. 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행한다.
     → 하나의 간선에 연결되어 있으므로 합집합 연산 수행
     b. 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것으로 판단할 수 있다.
     → 하나의 간선에 연결된 두 노드가 루트 노드를 공유한다면 사이클이 발생한 것이다!!
     
  2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다. (모든 과정이 끝날 때 사이클이 발생하지 않았다면 사이클이 없다고 판단할 수 있다.)

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

Python 코드

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

# 연산 1 : 특정 원소가 속한 집합(루트 노드)를 찾아주는 연산 (find)
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 연산 2 : 두 원소가 속한 집합을 합치는 연산 (union)
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

# 입력
num_node, num_edge = map(int, input().split())
parent_table = [0] * (num_node + 1)

# 부모 테이블 초기화
for i in range(1, num_node + 1):
    parent_table[i] = i

# 사이클 판별
cycle = False # 사이클 발생 여부

for i in range(num_edge):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우
    if find_parent(parent_table, a) == find_parent(parent_table, b):
        cycle = True
        break
    # 사이클이 발생하지 않은 경우
    else:
        union_parent(parent_table, a, b)

# 출력
if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")