[혼자 공부한] 분리집합

분리집합이라는 말을 들었을 때, Disjoint Set이라는 단어가 일단 생각이 났다.

 

아무리봐도 Intersection이 없는 집합들 이라고 생각할 수 있겠다.

 

사실 백준에서 문제 하나를 풀고 있었는데, 이거 태그가 분리집합이라서 ... 공부를 해야겠다고 생각하게 된듯.

 

즉, [1,2,3,4,5,6] 같은 집합이 주어져있을 때, 이들을 어떻게 묶을 것인지? 

 

어떻게 보면 Strongly Connected Component들이 구성되어있는가? 가 되겠다.

 

먼저 이러한 분리 집합을 생각함에 있어서 Union - Find라는 두개의 function을 통해서 정의된다.

 

첫번째로, Find (특정 원소가 어디에 소속되어있는지?)

 

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

 

이런 방식으로 재귀를 통해 x의 parent를 찾아가는 과정을 취한다.

 

다음으로는, 두개의 분리집합을 합치는 과정이 되고, Union이다.

def union(parent,a,b):
	a = find(parent, a)
    b = find(parent, b)
    if a < b:
    	parent[b] = a #작은쪽으로 맞추기 위해
    else:
    	parent[a] = b #작은쪽으로 맞추기 위해

 

이제 이러한 개념을 알아뒀으니 ,,,, 못풀었던 문제들을 해결하기 위해 떠나봐야겠다.

 

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