Ray`s Tech Lab

분리집합(Disjoint Set)이란 서로 중복되지 않는 부분집합들로 나뉜 원소들에 대한 정보를 다루는 자료구조이다. Union-Find 알고리즘은 이 자료구조를 활용하는 대표적인 그래프 알고리즘 중 하나로, '합집합을 찾는다'라는 의미를 가진다. 디테일하게 들어가면 원소 x, y를 고른 다음 x가 속한 집합과 y가 속한 집합이 같은지 판별하는 알고리즘안대, 이는 여러 노드가 존재할 때 내가 선택한 임의의 두 노드가 서로 같은 그래프에 속하는지 판별한다는 것과 같은 개념으로 생각할 수 있다.

그냥 내가 이해한대로 쉽게(나름대로) 설명하자면, Union-Find알고리즘과 분리집합은 집합을 표현하는 하나의 형태이다. 1부터 5까지의 원소들이 있고 이들이 각각 집합의 형태를 이루고 있다고 하자. 즉,

{1}, {2}, {3}, {4}, {5}

이렇게 있는 것이다. 근데 이를 표를 통해 다음과 같이 표현할 수 있다.

{1}의 입장에서 자기가 속한 집합의 리더는 자기 자신(1)이고, {2}나 다른 애들 입장에서도 마찬가지다. 즉 표를 통해 자신이 속한 집합의 리더를 나타내준것! 근데 여기서 {1}과 {2}가 만나서 합집합 {1, 2}를 만들어냈다고 하자. 1과 2가 같은 집합의 원소로 구성된 것이다. 현재 존재하는 집합들은

{1, 2}, {3}, {4}, {5}

인 것이다. 이는 방금과 같은 표를 통해 어떻게 표현할 수 있을까?

다른 건 변함없고 2만 변화가 생겼다. 자신이 속한 그룹의 리더가 1이 된 것! 사실 뭐 2를 리더로 할 수도 있지만..집합을 이루는 원소 중 가장 작은 놈을 리더로 뽑는 것이다. 쉽게 생각해서 2는 1이 이끄는 집합의 멤버가 된 것이라고 생각해도 된다. 만약 다른 애들도 서로 합치고 지지고 볶고 해서 집합들이 다음과 같이 됐다면?

{1, 2}, {3, 4, 5}

표는 다음과 같아질 것이다.

그럼 생각해보자. 내가 임의로 두 원소를 뽑았는데 그 놈이 2랑 4다. 이들이 각각 속한 집합은 같은가?

표를 통해서 다르다는 것을 알 수 있다. 왜 Why? 2는 1이 이끄는 집합에 속해있고, 4는 3이 이끄는 집합에 속해있기 때문이다. 서로가 속한 집합의 리더가 다르기 때문에 이들이 속한 집합은 서로 다른 집합이다라고 말할 수 있는 것이다. 이것이 Union-Find알고리즘이다. 

근데 Union Find알고리즘은 여러 노드가 존재할 때 두 노드를 선택해서 이 두 녀석이 같은 그래프에 속하는지 판별하는 것으로도 이해할 수 있다고 했다. 간단하다. 단지 집합으로 표현하던 걸 그래프로 나타낼 때 Union Find가 저렇게 표현될 뿐이다. 1~5까지의 각 원소들이 집합의 형태를 이루고 있는 상태를, 1~5까지의 노드들이 서로 연결되지 않고 존재하는 상태라고 이해하면 된다. 그리고 집합들이 합쳐지는 것은 노드들 간에 연결선이 생겨서 연결되는 것으로 생각하면 된다. 따라서 내가 고른 임의의 두 노드가 서로 같은 그래프에 존재하는지 확인하는 것은 각각의 root노드들을 확인해서 같으면 같은 그래프 상에 존재하는 것이다! ...사실 이 부분은 글로만 써서 이해가 잘 안 될 수도 있으니 공부할 때 참고한 나동빈 님의 영상을 링크로 걸어두겠다.

https://www.youtube.com/watch?v=AMByrd53PHM 

그럼 Union Find를 파이썬으로 구현해보자.

parant = [i for i in range(n + 1)]

def getParant(x):         # x의 부모를 리턴하는 함수
    if parant[x] == x:    # x의 부모가 자기자신이라면 x를 그대로 리턴
        return x        
    parant[x] = getParant(parant[x])  # x의 부모가 자기자신이 아님 -> 재귀호출로 x의 부모 재설정
    return parant[x]                  # 최종적으론 x의 부모 리턴
    
def union(x, y):        # x가 속한 집합과 y가 속한 집합 합치기 - 가장 부모을 비교해 더 작은 쪽으로 합침
    x, y = getParant(x), getParant(y)
    if x < y:           # x가 더 작으니까 y의 부모를 x로
        parant[y] = x
    elif x > y:         # y가 더 작으니까 x의 부모를 y로
        parant[x] = y

def hasSameParant(x, y):         # x, y가 같은 부모를 같는지 즉 같은 집합에 속해있는지
    x, y = getParant(x), getParant(y)
    if x == y:
        return "YES"
    else:
        return "NO"

리더로 표현하던 것을 부모로 표현하는 것에만 차이가 있다. getParant함수가 이 알고리즘의 핵심으로 자신의 부모가 자기자신이 아니라면 재귀호출을 통해 자신의 부모를 최상단 노드, 즉 집단 내에서 가장 작은 놈으로 설정해준다.  이를 통해 백준 사이트에서 대표적으로 다음과 같은 문제를 풀 수 있다.

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