[알고리즘] 분리 집합

분리 집합(Disjoint Set, Union-Find)은 많은 알고리즘 코딩 테스트에서 중요한 자료구조로 나타납니다. 분리 집합은 여러 노드가 서로 중복되지 않는 집합으로 나뉘어 있을 때, 각 집합을 대표하는 노드 하나를 선택해 그 집합을 대표하도록 구성합니다.

분리 집합의 주요한 사용 용도는 다음과 같습니다:

1. 사이클 판별: 주로 그래프에서 사이클이 있는지 확인할 때 사용됩니다. 간선을 하나씩 추가하면서 두 노드의 루트 노드가 같다면 사이클이 생성되는 것입니다. Kruskal 알고리즘에서 최소 신장 트리를 구할 때 사이클 확인 용도로 사용됩니다.
2. 집합의 병합 및 찾기 연산: 두 집합을 하나로 합치거나, 어떤 원소가 어떤 집합에 속하는지 찾을 때 사용됩니다.
3. 네트워크 연결: 여러 네트워크가 연결되어 있을 때, 두 네트워크가 연결되어 있는지 확인하거나 연결할 때 사용됩니다.
4. 모양 인식: 이미지나 그래프에서 같은 모양의 그룹을 판별하는 문제에서 사용될 수 있습니다.
5. 동등 관계 문제: 두 원소가 같은 집합에 속해 있는지 확인하는 문제에서 사용됩니다.

분리 집합을 사용하여 문제를 해결할 때 주로 다음 두 가지 주요 연산을 사용합니다:

• Union: 두 원소가 속한 집합을 합칩니다.
• Find: 원소가 속한 집합의 대표 원소(루트 노드)를 찾습니다.

분리 집합은 경로 압축 기법 등의 최적화를 통해 매우 효율적으로 동작하며, 그래서 많은 코딩 테스트나 알고리즘 문제에서 유용하게 사용됩니다.

 

예시 문제

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

20040번: 사이클 게임

# 20040번 사이클 게임
# 사이클이 생기는지에 대한 확인을 위해 분리집합을 사용할 것이다. bfs는 시간소모가 너무크다.
import sys

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

def union(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

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

ans = 0
for i in range(m):
    x, y = map(int, sys.stdin.readline().split())
    # 부모가 같다면 사이클 구성한다.
    if find_parent(x) != find_parent(y):
        union(x, y)
    else:
        ans = i + 1
        break
print(ans)