[Algorithm] 서로소 집합이란?

주요 개념

• 서로소 집합은 크루스칼 알고리즘에 핵심 개념으로 사용됩니다.
• 서로소 집합은 공통 원소가 없는 두 집합을 의미합니다.
  • 예를 들어, 집합 {1, 2} 와 {3, 4} 는 서로소 관계입니다.
• 서로소 집합은 2가지 연산(union, find)으로 조작할 수 있습니다.
  • union 연산은 2개의 부분 집합을 하나의 집합으로 합치는 연산입니다.
  • find 연산은 특정한 원소가 어떤 집합에 속해있는지 알려주는 연산입니다.
• 따라서, 전체 요소들이 주어졌을 때, 전체 요소들이 어떤 형태의 부분 집합으로 나누어지는지 확인하고 싶을 때 사용하는 개념입니다.

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

• 여러 개의 Union(A, B) 연산이 주어집니다.
• 순서대로 Union(A, B) 연산을 진행합니다.
  • find 를 사용해, A와 B의 루트 노드인 A’, B’ 를 각각 찾습니다.
  • A’, B’ 중 작은 값을 A와 B의 루트 노드로 동일하게 설정합니다.
• 여러 개의 Union 연산이 끝나면, 전체 요소들이 어떤 부분 집합에 속해있는지 찾습니다.
  • find 를 사용해, 모든 parent 값들을 루트 노드로 변경합니다.
• 알고리즘에 대한 세부 설명은 아래 예제 코드와 같습니다.

주의 사항

• 결과 부분 집합은 Union 연산 순서에 따라 달라질 수 있습니다.

예제 코드

# x가 속한 집합을 찾기
def find_parent(parent, x):
    # 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=' ')

6 4
1 4
2 3
2 4
5 6

각 원소가 속한 집합 : 1 1 1 1 5 5
부모 테이블 : 1 1 1 1 5 5

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

• 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다는 특징이 있습니다.
  • 참고로, 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있습니다.
• 그래프의 간선을 하나씩 확인하면서, 각 간선의 두 노드에 대한 union 연산을 통해 사이클을 판별할 수 있습니다.

사이클 판별 동작 과정

• 각 간선을 확인하며 두 노드의 루트 노드를 확인합니다.
  • 루트 노드가 서로 다르다면, 두 노드에 대하여 union 연산을 수행합니다.
  • 루트 노드가 서로 같다면 사이클이 발생한 것입니다. (중요)
• 그래프에 포함되어 있는 모든 간선에 대하여 위 과정을 반복합니다.

예제 코드

# x가 속한 집합을 찾기
def find_parent(parent, x):
    # 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

사이클이 발생했습니다.

참고

• https://www.youtube.com/watch?v=aOhhNFTIeFI