[자료구조] 서로소 집합 (Disjoint Sets), 사이클 판별 알고리즘

• 서로소 집합: 공통 원소가 없는 두 집합을 의미한다.

 

1. 서로소 집합 자료구조

서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.

합치기 찾기(Union-find) 자료구조라고 부르기도 한다.

 

이미지 1

✔️연산

• 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
• 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

 

✔️ 동작 예시

1) 합치기 연산

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

 

이미지 2

 

✔️ 기본 소스 코드 예제

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

# 두 원소가 속한 집합 합치기(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


# 노드의 개수와 간선(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=" ")

 

• 해당 구현 문제점
  • 최악의 경우 (합집합 연산이 편향되게 이루어지는 경우) 찾기(Find) 함수가 O(V)

 

✔️ 경로 압축 (Path Compression) : 찾기 연산 최적화

 

찾기(Find) 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신한다.

 

# 특정 원소가 속한 집합을 찾기
# 경로 압축 방법
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

 

• 각 노드에 대해 찾기(Find) 함수를 호출한 이후에 해당 노드의 루트 노드가 바로 부모 노드가 된다.
• 모든 합집합(Union) 함수를 처리한 후 각 원소에 대하여 찾기(Find) 함수를 수행하여 부모 테이블이 갱신된다.

 

 

2. 사이클 판별 알고리즘

무방향 그래프 내에서의 사이클을 판별할 때 서로소 집합을 사용할 수 있다.

 

✔️ 동작 예시

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

 

 

0. 초기화

인덱스	1	2	3
부모	1	2	3

1. 간선 (1,2) 확인

같은 집합에 속하도록 함. (Union 연산)

인덱스	1	2	3
부모	1	1	3

2. 간선 (1,3) 확인

인덱스	1	2	3
부모	1	1	1

3. 간선 (2,3) 확인

루트 노드를 확인했을 때 이미 같은 루트 노드이다. 

-> 사이클 발생

 

 

✔️ 소스 코드 예제

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

# 두 원소가 속한 집합을 합치기 (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

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())

# 초기 상태에서 모든 노드의 루트 노드를 자신으로 초기화
parent = [i for i in range(v+1)]

# 사이클 발생 여부
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("사이클이 발생하지 않았습니다")

 

---

✔️ 관련 문제

• [백준, 16562] 친구비

---

📌 Reference & Additional Resources

• [한빛미디어] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)
• 이미지 1 출처: 끄적끄적 노트님 티스토리, 포스팅