[WEEK03] 서로소 집합 자료구조

서로소 집합 자료구조 

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

union, find 2개의 연산으로 조작할 수 있음 => union - find 자료구조라 부름

 

 

특징

- 서로소 집합 자료구조를 구현할 때 트리 자료구조를 이용하여 집합을 표현하는데

  서로소 집합 정보 (합집합 연산)이 주어졌을 때 트리자료구조를 이용해서 집합을 표현하는

  서로소 집합 계산 알고리즘은 다음과 같음

 

  1) union(합집합) 연산을 확인하여 서로 연결된 두 노드 A, B를 확인

      - A와 B의 루트 노드 A', B'를 각각 찾음

      - A'를 B'의 부모노드로 설정 (B'가 A'를 가르키도록 함)

  2) 모든 합집합 연산을 처리할 때까지 1)의 과정을 반복

 

- 일반적으로 find, union 연산을 활용하면 시간복잡도가 O(VM)이 될 수 있음 (노드개수 V, 연산개수 M)

 

 

개선된 서로소 집합 알고리즘

# 특정 원소가 속한 집합을 찾기
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= ' ')

 

 

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

# 서로소 집합을 활용한 사이클 판별 소스코드
# 특정 원소가 속한 집합을 찾기
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("사이클이 발생하지 않았습니다.")

 

 

출처

서적 : 이것이 취업을 위한 코딩테스트다