다양한 알고리즘 - 서로소 집합(경로 압축 기법)

안녕하세요. 오늘은 이전에 다뤘던 기본적인 서로소 집합 알고리즘을 개선해 보려고합니다.

https://sonlife97.tistory.com/entry/%EB%8B%A4%EC%96%91%ED%95%9C-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

다양한 그래프 알고리즘 - 서로소 집합

 

기본적인 알고리즘을 사용하면 find 함수가 비효율적으로 동작합니다.

 

최악의 경우 find 함수가 모든 노드를 다 확인하는 터라 시간 복잡도가 O(V)라는 점입니다.

 

다음과 같이 {1, 2, 3, 4, 5}의  총 5개의 원소가 존재하는 상황에서 모두 같은 집합에 속하는 경우를 가정해봅시다.

 

구체적으로 4개의 union 연산이 순서대로 (4, 5), (3, 4), (2, 3), (1, 2) 와 같이 주어졌다고 해봅시다.

 

이때 차례대로 연산을 처리하게 되면 다음과 같이 일렬로 나열하는 형태가 됩니다.

 

 

 

아래는 주어진 연산들을 처리하면서 노드의 번호와 부모 결과를 나열한 것입니다.

초기에는 각 노드가 자기 자신을 가리키고 시작합니다.

 

계산 과정

1. 초기 상태: {1, 2, 3, 4, 5} (각 노드가 자기 자신을 가리키는 상태)

2. (4, 5) 연산 후:
   - 부모 테이블: [1, 2, 3, 4, 4]
   - 결과: {1, 2, 3, 4, 4} (5의 부모가 4로 업데이트)

3. (3, 4) 연산 후:
   - 부모 테이블: [1, 2, 3, 3, 4]
   - 결과: {1, 2, 3, 3, 4} (4의 부모가 3으로 업데이트)

4. (2, 3) 연산 후:
   - 부모 테이블: [1, 2, 2, 3, 4]
   - 결과: {1, 2, 2, 3, 4} (3의 부모가 2로 업데이트)

5. (1, 2) 연산 후:
   - 부모 테이블: [1, 1, 2, 3, 4]
   - 결과: {1, 1, 2, 3, 4} (2의 부모가 1로 업데이트)

node   : 1 2 3 4 5
parent : 1 1 2 3 4

 

위 그래프를 통해 알 수 있듯이 1부터 5까지의 모든 원소가 루트 노드로 1이라는 값을 가집니다.

 

하지만 실제로 부모 테이블에 감겨 있는 1부터 5까지의 노드에 대한 부모 노드 값은 차례대로 1, 1, 2, 3, 4가 됩니다.

 

예를 들어 노드 5의 루트를 찾기 위해서는 '노드 5 -> 노드 4 -> 노드 3 -> 노드 2 -> 노드 1' 순서대로 부모 노드를 거슬러 올라가야하므로 최대 O(V)의 시간이 소요될 수 있습니다.

 

결과적으로 현재의 알고리즘을 그래로 이용하게 되면 노드의 개수가 V개이고 find 혹은 union 연산의 개수가 M개일 때, 전체 시간 복잡도는 O(VM)이 되어 비효율적입니다.

 

 

하지만 이러한 find 함수는 아주 간단한 과정으로 최적화가 가능합니다. 

 

바로 경로 압축 기법을 적용하면 시간 복잡도를 개선시킬 수 있습니다.

 

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

 

기존의 find 함수를 다음과 같이 변경하면 경로 압축 기법이 구현됩니다.

# 기본 
def find_parent(parent, x):
    # 만약 현재 원소 x가 자기 자신을 가리키지 않는다면,
    if parent[x] != x:
        # 루트 노드를 찾을 때까지 재귀 호출하여 부모를 업데이트한다.
        return find_parent(parent, parent[x])
    # 루트 노드에 도달하면 그 값을 반환한다.
    return x



# 경로 압축 기법을 사용한 서로소 집합의 루트 노드 찾기 함수
def find_parent(parent, x):
    # 만약 현재 원소 x가 자기 자신을 가리키지 않는다면,
    if parent[x] != x:
        # 현재 노드 x의 부모 노드를 재귀적으로 찾고, 부모 테이블을 갱신하여 경로 압축 수행
        parent[x] = find_parent(parent, parent[x])
    # 최종적인 루트 노드 반환
    return parent[x]

 

기본 find_parent 함수

 

이 함수는 간단한 서로소 집합을 구현하는데 사용되며, 경로 압축 기업을 적용하지 않습니다.

 부모 노드를 찾을 때, 재귀적으로 부모를 찾아 올라갑니다.

 

하지만 경로압축을 하지 않기 때문에 각 노드의 부모 노드가 최상위 루트 노드에 도달 할 때까지 경로에 노드가 모두 나열됩니다.

 

따라서, 이 함수를 사용하면 서로소 집합의 루트 노드를 찾는데 시간 복잡도가 O(V)가 될 수 있습니다. (V는 노드의 개수)

 

경로 압축을 사용한 find_parent 함수

 

이 함수는 경로 압축 기법을 적용하여 효율적으로 서로소 집합을 구현하는데 사용됩니다.

 

부모 노드를 찾을 때, 재귀 호출을 통해 최종 루트 노드를 찾으면서, 중간에 있는 모든 노드의 부모를 최상위 루트 노드로 갱신합니다.

parent[x] = find_parent(parent, parent[x])

 

 

이 함수를 사용하면 서로소 집합의 루트 노드를 찾는 시간 복잡도가 거의 O(1)에 가깝게 됩니다.

 

이는 경로 압축으로 인해 각 노드의 부모가 최상위 루트 노드를 가리키게 되기 때문입니다.

 

 

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

# 서로소 집합을 구현하는 함수: find_parent
def find_parent(parent, x):
    # 현재 원소 x가 자기 자신을 가리키지 않으면
    if parent[x] != x:
        # 부모 노드를 재귀적으로 찾아서 경로 압축(Path Compression)을 수행한다.
        parent[x] = find_parent(parent, parent[x])
    # 최종적인 루트 노드를 반환한다.
    return parent[x]

# 두 원소가 속한 집합을 합치는 함수: union_parent
def union_parent(parent, a, b):
    # 각 원소 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=' ')