티스토리 뷰
문제 보기
기본적으로 Disjoint를 알면 쉬운문제, 근데 애초에 엘리먼트 크기가 1,000,000 이므로 disjoint 말고는 풀수 있는 경우가 딱히 없을듯하다.
대표적인 Dis-joint set 문제이다. 또는 Union Find 문제라고도 불린다. disjoint 는 집합에서 공통된 원소가 없을 때 두 집합이 disjoint 하다고 표현한다.
일단 제 포스트보다 더 설명 잘되있는 곳을 소개해드립니다.
대충 어떤거냐면, Union Find에서 대충 알수 있듯이... 왠지 Union (합집합) 시키고 Find(찾기) 하는거 같다. 근데 이 구조를 어떤 구조를 이용하냐면, tree 구조를 이용하고, 그 tree 탐색을 하는데 dfs 와 비슷하게 한다. 그래서 분류도 dfs and simillar로 하게되었다.
우선 두 원소가 지칭 될 때 그 두 원소를 합치는 것이 union 의 역할이다. union의 역할은 하나의 원소의 root(부모)를 찾아서 그 것을 다른 녀석에 연결하는 것이다. 이게 말은 뭐지.. 왜 집합이라했는데 트리구조가 나오니 라면서... 어려울거같은데 함수는 짱짱쉽다. 그리고 집합이 합집합이 된다는게 그냥 하나의 원소를 루트로 잡고 그 하나 주위로 다 자식으로 붙이면 되는것이 개념적으로 쉽기 때문이다.
find(n) 을 n원소의 root 원소를 찾는다고하자. 두 원소가 x, y 일 경우 y가 속한 집합을 x가 속한 집합에 포함시킨다고 하자. 스도코드는 이럴것이다.
find(y).child = find(x);
그러니까 y가 속한 집합의 root부모 의 자식으로 x가 속한 집합의 root부모 만 넣어주면 자연스레 x가 원래 포함하고 있는 모든 원소들이 y가 속한 집합으로 포함되게 되는것이다. 또 반대로는 이렇게도 표현할 수 있을것이다.
find(x).parent = find(y); 이거는 x의 root를 찾아 그 것의 부모를 y의 root로 만든다는 것이다. 그게그거다... (사실은 집합을 합친다는 것이 우리가 할것인건데, 트리를 합친다고 표현하는게 쉬우니까... 그게 바로 disjoint set, union find, 트리 구조다.)
설명하다보니 union과 find 다 설명하게되었다.
일단 우리는 parent 배열을 생성하고, 각 원소의 parent를 자기 자신으로 설정해준다.
우리가 설명한 find 함수는 다음과 같이 생겼다. 코드가 짧아서 구냥 다올려보았다.
find함수는 재귀적으로 탐색하며 자신의 부모를 찾아서 내려간다. 이 부분이 dfs와 닮았다.
다음 배열을 확인해보자
parent 배열
1 2 3 4 5
5 4 1 4 5
그렇담 이렇게 되있는 것이다.
(parent) 5 - 1 - 3 (child)
(parent) 4 - 2 (child)
find (3)은 어떻게 동작하나? 최종 부모인 5를 반환한다.
find (3){
else return find(parent[3]==1){
else return find(parent[1]==5){
<-------- return 5
a 와 b를 union 하는 과정은 다음과 같다.
parent[find(a)]=find(b) a의 root의 root를 b의 root로 두는것이다.
parent 배열
1 2 3 4 5
5 4 1 4 5
(parent) 5 - 1 - 3 (child)
(parent) 4 - 2 (child)
인 상태에서 1이 포함된 집합을 2가 포함된 집합과 합친다고 해보자.
1의 root를 찾아서 "find(1)" 그녀석의 parent를 "parent[find(1)]" 바로 원소 2의 root "find(2)"로 설정한다.
그렇담 parent 배열은 다음과같이된다.
parent 배열
1 2 3 4 5
5 4 1 4 4
find(3){
else return find(parent[3]==1){
else return find(parent[1]==5){
else return find(parent[5]==4){
<--------------return 4;
ufind(3){
else return parent[3]=ufind(parent[3]==1){
else return parent[1]=ufind(parent[1]==5){
parent[3],[1](갱신) < return 5;
ufind(2){
else return parent[2]=ufind(parent[2]==4){
parent[2](갱신) < return 4;
parent 배열
1 2 3 4 5
5 4 5 4 4
자 여기서 3의 원소와 원소 5가 같은 집합인지 확인해보자
ufind(3) == ufind(5)?
ufind(3){
else return parent[3]=ufind(parent[3]==5){
else return parent[5]=ufind(parent[5]==4){
parent[3],[5](갱신) < return 4;
ufind(5){
else return parent[5]=ufind(parent[5]==4){
parent[5] (갱신) < return 4;
이 녀석들이다. 3은 한번 더 위로 올라와서 4바로 밑의 자식으로 붙어버렸다. 이렇게 되도 상관없다. 우리는 자식과 부모를 따지려는게 아니라 한 집합을 표현하기위해 트리로 묶는 구조를 이용했기 때문에, tree가 더 깊이 내려가지 않고 높이가 좀 더 줄으면 줄을 수록 연산속도에 더 좋은것이다.
이 union find tree의 재귀 구조는 어디까지 줄어들수 있을까? 당연히 높이 1까지 줄어들수 있다. 다음과 같다.
4 - 2
+ 5
+ 3
+ 1
신기하다.
어떤 초기 원소가 자기 자신이 한 집합을 대표하는 root가 아니라면 자신의 parent 를 항상 호출하며 갱신하는데 그것도 root가 아니라면 parent의 parent를 찾고 또 그것이 root까지 올라가 결국 초기 원소를 포함한 그 것의 모든 parent를 root로 갱신하는 것이다. 단 초기 원소의 자식은 아니고...
ufind 함수가 해당 녀석이 포함된 집합 ( 정확하게는 그 집합을 대표하는 root 원소)를 반환할 때마다, 그 녀석, 그리고 그녀석의 parent, 그리고 그 parent의 parent, 또 그 parent의 parent... 계속해서 결국 root 원소까지 나올때까지 그 들의 parent를 현재 root로 갱신한다.
말이 베베꼬였는데, 어쨌든, "지가 한집합을 대표하는 root가 아니면, root 까지 거슬러 올라가고 그 거처간 녀석들의 parent를 root로 갱신한다 그래서 결국 집합을 표현하는 root의 깊이가 져낸 짧아진다 최대 높이가 1까지 줄어든다." 소스는 더 쉽다.
소스보기
'알고리즘 문제 > DFS and Simillar' 카테고리의 다른 글
백준 12784 인하니카 공화국 (0) | 2018.05.29 |
---|---|
백준 2447 별찍기10 (0) | 2018.03.06 |
884C Bertown Subway (0) | 2017.11.05 |
- Total
- Today
- Yesterday
- beginning javascript
- 최단경로 알고리즘
- 그라파나
- 자바스크립트
- javascript
- Propositional and Predicate Logic
- 자바스크립트 예제
- 조합 코딩
- paul wilton
- Arena
- 시뮬레이션
- 이산 수학
- 이산수학
- 아레나
- arena simulation
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- Trie
- 아레나시뮬레이션
- 대규모 시스템 설계 기초
- grafana cloud
- Discrete Mathematics
- Simulation
- rosen
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 로젠
- 데이터 중심 애플리케이션 설계
- 명제논리
- 아레나 시뮬레이션
- flutter
- 백준
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |