[코딩테스트 cheatsheet] 서로소 집합 (Disjoint set)

개념

서로소 집합 : 공통 원소가 없는 두 집합

서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

 

스택, 큐가 pop, push 연산을 사용하는 것 처럼 서로소 집합은 union, find 연산을 이용함

find - 속한 집합이 어떤 집합인지 찾기

union - 두 개의 집합을 합치기

 

싸이클인지 구하기 

find해서 같다면 cycle

다르면 union

코드

# find - 부모 찾기
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[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
 
v, e = map(int, input().split())
parent = [0] * (v + 1)

# 부모를 자기 자신으로 초기화, 문제에 따라 다름
for i in range(1, v + 1):
    parent[i] = i
    
# 입력마다 바로 union 해주면 됨
for _ in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)
    
# 마지막에 모든 노드에 대해서 find
for i in range(1, v + 1):
    find_parent(parent, i)
    
# cycle 구하기
cycle = False
for i in range(e):
    a, b = map(int, input().split())
    if find_parent(parent, a) == find_parent(parent, b):
    	cycle = True
        break
    else:
    	union_parent(parent, a, b)

 

백준 티어별로 살펴보는 문제 유형

 

골드 4

알면 풀리는 문제

1717 - 집합의 표현 (https://www.acmicpc.net/problem/1717)

 

골드 3

 

골드 2

살짝만 생각하면 풀리는 문제

10775 - 공항 (https://www.acmicpc.net/problem/10775)