Union find 알고리즘 - Python

대표적인 그래프 알고리즘.

오늘은 Union find 알고리즘에 대해 알아보겠습니다.

이번글은 아래의 자료를 참고했습니다.

1. TopCoder 알고리즘 트레이닝
2. Union find 알고리즘 블로그 1

 

이 글에서 알아볼 내용

1. Union find 알고리즘
2. 핵심 아이디어
3. 예제 문제
4. 마치면서

 

Union find 알고리즘

기본적으로 Union-find 알고리즘은 자료구조라고 볼 수 있습니다. 그래서 Disjoint Set (상호배타적인 집합) 이라고 불리기도 하는데요. 아래의 그림을 통해 간단히 파악해봅시다.

어떤 차이가 있는지 파악하셨나요? 상호배타적 집합은 같은 그룹에 속하지만 공통점은 없는 집합을 뜻합니다. 그리고 Union-find는 이런 상호배타적 집합에서의 데이터 조작을 하는 자료구조 입니다. 그렇다면 이런 자료구조는 왜 필요할까요? 

 

어떤 정점과 정점의 연결을 어떻게 파악할 수 있을까요? BFS, DFS 와 같은 탐색으로도 연결을 파악할 수 있습니다. 하지만 할때마다 O(n)이라는 완전탐색을 거쳐야하죠. 이는 굉장히 비효율적입니다. 하지만 만약 이들을 그룹으로 묶으면 어떨까요? 그룹 안에 있는 노드들은 모두 연결되어 있다는 것을 쉽게 파악할 수 있습니다. 그리고 이것을 Union-find 는 효과적으로 구현할 수 있게 해줍니다. 그룹을 쉽게 구성할 수 있게 해주는 것이죠. 핵심 아이디어는 아래에서 보도록 하겠습니다.

 

핵심 아이디어

위에서도 말했다시피. Union-find 알고리즘은 그룹을 구성하게 해줍니다. 그렇다면 어떤 과정을 거쳐야 할까요? 크게 3가지가 있습니다.

 

1. makeset : X 만을 가지는 집합을 초기화 한다.
2. find : 해당 노드가 어떤 그룹(집합)에 속하는지 파악한다.
3. union : 두 개의 집합을 하나로 합친다.

 

간단히 말하자면. 초기화하고 찾고 합친다. 이게 Union-find 의 알고리즘의 전부입니다. 아래의 그림을 통해 이 과정을 살펴봅시다.

 

그래프 그림 1

 

대강 이런 그래프가 있다고 해봅시다. 우리 눈으로 보면 다 연결되어 있다는 것을 쉽게 알 수 있지만. 컴퓨터로 연결됐다는 것을 파악하기는 꽤나 귀찮아집니다. 이걸 컴퓨터가 알아먹기 쉽게 바꿔봅시다.

 

그래프 그림 2

 

이렇게 하면 훨씬 알아보기 쉬워집니다. 이 과정이 바로 Union-find 의 과정입니다. 간략하게 표현하자면 다음과 같습니다.

 

1. 각각 노드의 부모(그룹)를 확인한다. (find)
2. 현재 부모의 값보다 비교한 다른 부모의 값이 더 작다면 부모의 값을 변경한다. (union)
3. 위의 두 과정을 반복한다.

위에 있는 그래프 그림1 을 통해 한번 실행해보세요! 그러면 그래프 그림 2 의 그림을 도출해낼 수 있을 것 입니다. 이제 남은 것은 코드로 구현하는 것 입니다. 

 

예제 문제

문제는 간단합니다. {0, 1, 2, 3, 4, 5, 6} 이라는 상호배타적 부분집합을 Union find 알고리즘으로 그룹을 구성해볼 것 입니다. 아마 출력하면 ["-1, "0", "0", "0", "0", "0", "0"] 과 같은 값이 나오게 될 것 입니다.  그럼 한번 구현해보겠습니다.

 

def find(v, list_):
    if(list_[v] < 0):
        return v
    else: 
        list_[v] = find(list_[v], list_)
        return list_[v]

def union(from_, to, list_):
    from_ = find(from_, list_)
    to = find(to, list_)

    if(from_ is not to):
        list_[to] = from_

node = 7
list_ = [-1] * node

for i in range(node-1):
    union(i, i + 1, list_)

print(list_)

 

정말 간단한 코드입니다. union() 과 find() 를 집중해서 살펴보세요. find를 통해서 속해있는 그룹을 찾고. union에서는 그룹을 비교한다음 두 부분집합을 합칩니다. 이 과정을 반복하면 우리가 처음에 원했던 ["-1, "0", "0", "0", "0", "0", "0"] 를 도출해낼 수 있습니다. 0이라는 그룹에 모두 묶은 것이죠. 이제부터 직접 치시면서 익혀보도록 하세요!

 

마치면서

다음번에는 이런 Union-find 알고리즘을 이용해서. MST(최소 신장 트리) 를 구현하는 방법에 대해서 알려드리도록 하겠습니다. 피드백, 질문은 언제나 환영입니다. 긴글 읽어주셔서 감사합니다.