서로소 집합 알고리즘

 서로소 집합 알고리즘  

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

- 서로소: 공통 원소가 없는 두 집합

- union, find 2개의 연산으로 조작 가능

union 연산 (합집합) : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

find 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

 

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

 

서로소 집합 계산 알고리즘

1) A와 B 노드가 연결되어 있을 때
     a) A와 B의 루트노드 a, b 를 각각 찾는다.
     b) a를 b의 부모 노드로 설정한다. (b가 a를 가리키도록 한다)
         // 일반적으로 더 번호가 작은 원소가 부모 노드가 되도록 구현
2) 모든 union 연산을 처리할 때까지 1번 과정을 반복한다.

 

• [초기 단계] 노드의 개수 크기의 부모 테이블을 초기화한다. 모든 원소가 자기 자신을 부모로 가지도록 설정

• [Step 1] 노드 1과 노드 4의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 1과 4이므로 더 큰 번호에
  해당하는 루트 노드 4의 부모를 1로 설정한다

• [Step 2] 노드 2과 노드 3의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 2와 3이므로 더 큰 번호에
  해당하는 루트 노드 3의 부모를 2로 설정한다

• [Step 3] 노드 2과 노드 4의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 2와 1이므로 더 큰 번호에
  해당하는 루트 노드 2의 부모를 1로 설정한다

• [Step 4] 노드 5과 노드 6의 루트 노드를 각각 찾는다. 현재 루트 노드는 각각 5와 6이므로 더 큰 번호에
  해당하는 루트 노드 6의 부모를 5로 설정한다

• 결론 : 연결성을 통해 쉽게 집합 형태를 확인할 수 있음.

 

서로소 집합 알고리즘 소스코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return 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=' ')

 

실행 결과

문제점

위의 알고리즘을 그대로 이용하게 되면 노드의 개수가 V개이고 find 혹은 union 연산의 개수가 M개일 때, 전체 시간 복잡도는 O(VM)이 되어 비효율적임

 

 

 경로 압축 (해결방안)

- find 함수는 경로 압축 기법을 적용하면 시간 복잡도를 개선시킬 수 있음 

- 경로 압축은 find 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 갱신하는 기법

- 기존의 find 함수를 다음과 같이 수정하면 경로 압축 기법 구현이 완료

def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

이렇게 함수를 수정하면 각 노드에 대해 find 함수를 호출한 후에 , 해당 노드의 루트 노드가 바로 부모 노드가 됨

 

코드 수정 후 실행 결과

유의할 점

- union 연산을 효과적으로 수행하기 위해 '부모 테이블'을 항상 가지고 있어야 함

- 루트 노드를 즉시 계산할 수 없고, 부모 테이블을 확인하며 거슬러 올라가야 함

 

+) 서로소 집합을 이용해 사이클 판별도 가능

 

 

 

참조 (그림)

[이것이 코딩 테스트다 with Python] 33강 서로소 집합 자료구조

 

참고 서적

이것이 취업을 위한 코딩 테스트다 with 파이썬