[알고리즘] 유니온 파인드(Union-Find)

유니온 파인드 알고리즘이란?

그래프 알고리즘의 일종으로 상호 배타적 지비합, Disjoint-set이라고도 한다.

여러 노드 중 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지를 확인하는 알고리즘이다.

서로소 집합 자료구조의 연산 알고리즘은 다음과 같다.

1. union(합집합): 서로 연결된 두 노드 A, B를 확인한다.

- A와 B의 루트 노드를 찾는다.

- A와 B의 루트 노드 중

 

Union-Find알고리즘

서로소 집합 알고리즘이라고도 불린다.
서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.
서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다.
이 자료구조는 union과 find 2개의 연산으로 조작할 수 있따.
union은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다.
find연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

find연산

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x
-> 부모를 알기 위해서는 parent[x] = x 자기 자신이 되어야 한다.
그렇지 않으면 부모로 가기 위해 다른 노드를 가르키고 있기 때문이다.

union 연산

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-Find알고리즘
서로소 집합 알고리즘이라고도 불린다.

서로소 집합이란 공통 원소가 없는 두 집합을 의미한다.
서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다.
이 자료구조는 union과 find 2개의 연산으로 조작할 수 있따.
union은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다.
find연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

 

find연산

 

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x
-> 부모를 알기 위해서는 parent[x] = x 자기 자신이 되어야 한다.
그렇지 않으면 부모로 가기 위해 다른 노드를 가르키고 있기 때문이다.

union 연산

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

-> 서로 부모 노드를 가져온 다음, 둘 중 작은 값으로 부모를 지정한다.
이렇게 함수를 수정하면 각 노드에 대하여 find함수를 호출한 이후에, 해당 노드의 루트노드가 바로 부모노드가 된다.




+ 하지만 여기서 find함수는 조금 비효율적이다. 최악의 경우 한번 동작하는데 O(v)가 걸릴 수 있다.
이러한 find함수를 간단한 과정으로 최적화 시킨 것이 경로압축 기법이다.
경로 압축은 find함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 갱신하는 기법이다.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]