[Python] 유니온 파인드 (Union Find)

Saemi Min·2023년 3월 2일
0

Data Structure & Algorithm

목록 보기
12/17
post-thumbnail

유니온 파인드 알고리즘 (Union Find Algorithm)

개념

  • 그래프 알고리즘, 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘
  • 서로소 집합, 상호 베타적 집합(Disjoint-Set = 서로 공통 원소가 없는 집합)으로도 불린다.
  • 노드를 합치는 Union 연산노드의 루트 노드를 찾는 Find 연산으로 이루어진다.
    => 즉, 노드들을 합치고(Union), 부모를 찾아(Find) 서로소 집합(Disjoint-Set)을 찾아내는 알고리즘이다.
  • 트리 구조를 활용한다.

과정

  • 초기값
    8개의 단절된 노드들이 있다. 이 노드들은 배열에 자기 자신의 값을 갖고있다.

  • 1 2 노드를 연결하고 4 5 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연산을 할 때
루트 노드를 찾는 탐색과정을 통해 루트노드에 연결하는 과정을 거쳐
결과적으로 아래의 그림처럼 트리가 형성된다.


코드

find 연산은 부모 노드를 찾을 때까지 재귀적으로 호출한다.
union 연산은 두 원소의 부모 노드를 찾고 번호가 큰 노드가 번호가 작은 노드의 부모를 가리키도록 한다.
이를 효과적으로 수행하기 위해 '부모 테이블'을 항상 가지고 있어야 한다.

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

참고 사이트

개념 참고 사이트
코드 참고 사이트

profile
I believe in myself.

0개의 댓글