Union-Find와 Disjoint Set

분리집합(Disjoint Set)이란?

말 그대로의 의미로 서로가 서로를 전혀 포함하지 않는 집합이다. 우리가 수학에서 흔히 서로소 집합 이라고 부르는 것들이 분리집합이라고 한다. 교집합의 원소가 공집합인 경우가 있다.

Union-Find란?

자 그럼 여기서 Union-Find가 왜 나오느냐. Union-Find의 방식으로 서로가 서로의 분리집합임을확실히 할 수 있기 때문이다. Union-Find 알고리즘은 트리의 방식을 이용하여 각각의 집합을 구축한다. 각각의 집합은 서로가 서로소임을 입증하는 방법으로 각자의 루트노드가 같은지 다른지를 확인하는 과정을 거친다. 루트노드가 같다면 같은 집합으로 루트노드가 다르다면 다른 집합이다. 트리 어디에서 출발해도 같은 루트노드로 가게되어 있기 때문이다.

def findParent(node):
    if union[node] == node: #부모노드가 자기 자신이라면 자기 자신 반환(루트노드라는 뜻)
        return node
    return findParent(union[node]) #아니면 부모노드에서 다시 실행

만약 분리집합인 두 집합을 합치려면 2개의 트리를 하나로 합쳐서 하나의 트리로 만들면 된다. 여기서 트리의 자식노드의 숫자에 따라서 어떤 루트노드를 자식노드로 할 지 어느 정도의 고려가 필요하다.

def unionSets(nodeX, nodeY):
    if nodeX > nodeY:# 여기서는 그냥 노드의 값이 큰걸로 다 결정했다.
        union[nodeX] = nodeY
    else:
        union[nodeY] = nodeX

이렇게 하나의 트리가 되면 같은 집합에 있다는 증명이 되는 것이다

1717. 집합의 표현

import sys
sys.setrecursionlimit(10**6)

n, m = map(int,sys.stdin.readline().split())
parent = [i for i in range(n+1)]

def findParent(x):
    if parent[x] == x:
        return x
    return findParent(parent[x])

def unionChild(x,y):
    parentX = findParent(x)
    parentY = findParent(y)
    if parentX != parentY:
        if parentY > parentX:
            parent[parentX] = parentY
        else:
            parent[parentY] = parentX
    return

for i in range(m):
    order, a,b = map(int, sys.stdin.readline().split())
    if order == 0:
        unionChild(a,b)
    else:
        parentA = findParent(a)
        parentB = findParent(b)

        if parentA == parentB:
            print("YES")
        else:
            print("NO")

대표적인 분리집합 문제이다. 위의 방식을 활용하여 문제를 풀면 풀 수 있다.