유니온 파인드

 

연속된 구간 [p : q] 을 merge 하는 경우, 단순하게 p, p+1, ..., q 를 순서대로 merge 하면 정보의 낭비가 크다.

 

merge(p ... q) 를 위에서 언급한 작업이라고 하자.

 

 

단순히 merge(p ... q)를 하는 경우 -

 

merge(1, 4)

merge(3, 6)

 

3, 4에서 불필요한 작업을 반복해서 하게 된다.

 

정보의 낭비를 줄여보자.

 

merge(1, 4)

 

방향을 뒤집어 오른쪽을 root로 하여 merge 한다.

 

이제 구간 [3 : 6] 을 merge 해보자. 구현은 다음과 같이 하였다.

 

while (search(p) != search(q)) {
 	int next = search(p) + 1;
	merge(q, p);
	p = next;
}

 

p는 3을 가리키고, q는 6을 가리키고 있다.

 

첫 루프에서, 다음 그림과 같이 merge(q, p)가 일어난다.

 

이제 p는 기존 p (=3) 에 대해 search(p) 의 다음 index 를 가리킨다. 그 위치는 4 + 1, 5 이다.

 

좋은 예시를 드는 능력이 없어 별 효과 없어 보이지만, p = 4 일 때의 의미 없는 merge를 건너뛰었음을 알 수 있다.

 

4까지는 이미 p와 같은 그룹이었으므로 그다음 index 5로 바로 건너뛰어도 좋은 것이다.

 

 

좀 더 좋은 예시로, [1 : 10000]이 한 그룹일 때 [2 : 10005]를 merge 하라는 쿼리가 들어오면 3~10000 까지의 연산을 모조리 건너뛰게 된다.

 

 

boj.kr/14595 풀다가 배운건데 같이 스터디하는 선배가 그리디 알고리즘으로 4ms에 풀어버렸다. 정말 대단하다..