Union-Find(합집합 찾기) 자료구조 - 작성중

Union-Find

개요

집합에는 두가지 종류의 연산이 필요

• membership 연산: 집합에 포함된 값인지
• 합집합(Union), 교집합(Intersection), 차집합(Difference)

파이썬에서는 Set을 통해 집합을 표현할 수 있다. 

Dict도 가능하지만 중복 key에 대한 처리를 해줘야 함으로 Set이 더 효과적

 

집합의 함수

집합에는 다음과 같은 함수들이 필요하다.

• make-set(x)
  -> x만으로 구성된 집합을 정의(make)
• find(x): membership fn
  -> x가 속한 집합의 대표값 리턴
  ex) 두 집합 S, T가 있을 때, find(5)라고 한 경우 T에 5가 포함되어 있다면 T를 대표하는 값을 리턴
• union(x, y)
  -> 두 key 값 x, y를 하나의 집합으로 합침. 만약 둘 다 이미 한 집합 안에 있다면 아무 행위도 하지 않음

 

• make-set 함수는 O(1). 즉, 상수 시간 내로 이루어지고
• find(x), union(x, y)는 O(logN) 내에 동작하게 하는게 1차 목표가 된다. 

위 세개의 연산을 어떤 자료구조로 구현할 수 있을지 알아보자. 

 

 

 

 

 

 

 

https://c4u-rdav.tistory.com/44

[파이썬으로 배우는 알고리즘] Union-Find 알고리즘

 

 

해시를 활용한 Union-Find 알고리즘 문제를 통해 활용해보자

 

문제 예시

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

4195번: 친구 네트워크

 

코드

def find(x):
  # if parent[x] != x:
  #   return find(parent[x])
  # return x
  if parent[x] != x:  # 경로 압축
    parent[x] = find(parent[x])
  return parent[x]

def union(x, y):
  x, y = find(x), find(y)
  if x != y:
    parent[y] = x
    count[x] += count[y]

for _ in range(int(input())):
  parent, count = {}, {}
  for _ in range(int(input())):
    x, y = input().split()
    if x not in parent:
      parent[x] = x
      count[x] = 1
    if y not in parent:
      parent[y] = y
      count[y] = 1
    union(x, y)
    print(count[find(x)])

 

추가 문제

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

20040번: 사이클 게임

* union-find는 크루스칼 알고리즘 등에서 사이클을 체크하는 용도로도 사용된다.

union-find의 union 연산에서 사이클인지 여부를 확인할 수 있는데 이는 무방향 그래프

 

쉬운버전

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

11724번: 연결 요소의 개수