[혼자 공부한] 분리집합
2024. 8. 15. 19:15ㆍ스터디
분리집합이라는 말을 들었을 때, 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 #작은쪽으로 맞추기 위해
이제 이러한 개념을 알아뒀으니 ,,,, 못풀었던 문제들을 해결하기 위해 떠나봐야겠다.
'스터디' 카테고리의 다른 글
4주차 스터디(23.12.01)-2 (1) | 2023.12.01 |
---|---|
4주차 스터디(23.12.01) (1) | 2023.11.30 |
3주차 스터디(23.11.24) (0) | 2023.11.30 |
2주차 스터디(23.11.16) - DFS, BFS (0) | 2023.11.11 |
1주차 스터디(23.11.09) - 완전 탐색 (Brute Force) (0) | 2023.11.07 |