[Algorithm] 유니온 파인드(Union-Find)란?? python에서 구현하기

🚀  들어가며...

• 백준 1647번 문제인 도시분할계획 문제를 풀다가 유니온 파인드 개념에 대한 이해와 활용이 필요하여 정리하였습니다.

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

📑 내용

유니온 파인드란?

• 유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘입니다.
• 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어집니다.

 

# 유니온 파인드

8개의 단절된 노드들이 있습니다.
이 노드들은 배열에 자기 자신의 값을 가지고 있습니다.

이 중에 1 2 노드를 연결하고 4 5 6 노드들을 연결하고 싶다고 가정해봅시다.

우선 1 2 노드를 합쳐봅니다.
합치는 방법은 간단하다 2번 노드의 배열 값을 1번 노드의 배열 값으로 바꿔주면 됩니다.

4 5 6도 마찬가지로 바꿔봅시다
4와 5를 연결하고 5와 6을 연결하면 그림처럼 배열이 바뀝니다.

이제 어떻게 노드들이 연결되어 있는지 아닌지 판별할 수 있는지 감이 오실겁니다.
예를들어 2번과 6번 노드가 연결되어 있는지 확인하고 싶다면

• 2번 노드의 부모를 찾는 과정
  1. 배열의 2번에 있는 값을 확인합니다. => 1번입니다.
  2. 배열의 1번에 있는 값을 확인합니다. => 1번입니다.
  3. 배열의 인덱스와 값이 일치합니다.
  4. 그렇다면 1번 노드가 2번 노드가 속해있는 트리의 루트 노드입니다.
• 6번 노드의 부모를 찾는 과정
  1. 배열의 6번에 있는 값을 확인합니다. => 5번입니다.
  2. 배열의 5번에 있는 값을 확인합니다. => 4번입니다.
  3. 배열의 4번에 있는 값을 확인합니다. => 4번이다.
  4. 배열의 인덱스와 값이 일치합니다.
  5. 4번 노드가 6번 노드가 속해있는 트리의 루트 노드입니다.

이제 각각 노드의 루트 노드를 비교해서 서로 다르다면 두 노드는 연결되어 있지 않은 것입니다.

하지만 이렇게만 바꾸면 문제가 발생합니다.

위의 예처럼 트리의 문제 중 하나인 한쪽으로만 자식이 몰려있는 편중현상이 생길 수 있습니다.
Find연산에서 재귀를 통해 루트 노드를 찾아야하는데 이렇게 편중되어 있으면 탐색하는데 시간이 많이 걸립니다.

위의 편중 문제를 해결하기 위해 합치는 Union연산을 할 때
루트 노드를 찾는 탐색과정을 통해 루트노드에 연결하는 과정을 거쳐
결과적으로 위의 그림처럼 트리가 형성됩니다.

1 2 를 연결하고 4 5 6을 연결한 유니온 파인드의 트리구조입니다.

이제 1과 4번 노드를 연결하고 싶다면 위의 그림처럼 바뀔 것입니다.

 

# Python 에서의 유니온 파인드 구현

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

# 두 원소가 속한 집합을 합치기
def union(a, b):
    a = find(a)
    b = find(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(a, b)

# 각 원소가 속한 집합 출력하기
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find(i), end=' ')

print()

# 부모 테이블 내용 출력하기
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

find 함수 부분을 '경로 압축' (Path Compression) 을 통해 다음과 같이 리팩토링 할 수 있습니다.

시간 복잡도가 감소하므로 이 코드를 사용하는 것이 좋습니다.

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

 

🙋🏻‍♂️ 후기

다음글에서는 백준 1647번 문제 풀이와 함께 돌아오겠습니다!

 

🔗  참고한 글

https://reinvestment.tistory.com/74

[Algorithm] Union - Find (Python 구현)