Union-find

union-find로 푸는 문제들

사실 union find 자체는 그렇게 어려운 아이디어는 아니다.

활용할 때도 보통 "union find가 잘 합쳐주는 작업을 O(1)에 해준다"을 쓰지 더 어렵게 활용하지는 않는다.

 

#1717 집합의 표현

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

문제 자체가 union find를 표현하는 문제

 

#1197 최소 스패닝 트리

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

아무래도 MST를 만들 때 union find를 이용해서 보통 만든다. (크루스칼 알고리즘)

 

<<< 내 생각에 이쯤에 합치기를 '잘' 해야하는 문제가 하나 들어가야 할 것 같다. >>>

항상 merge할 때 아무렇게나 p[y] = x 해야만 하는 것이 아니다.

예를 들어, 반드시 큰 그룹에 작은 그룹을 합쳐야만 한다면

size_Group(x) < size_Group(y) 면 swap(x, y)를 통해서 항상 큰 그룹에 작은 그룹이 합쳐지게 할 수 있다.

다만 너무 흔한 DSU와 관련된 주제라 이는 이 글을 제외한 모든 DSU 활용 글에서 찾을 수 있을 것이다.

 

#2887 행성 터널

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

이런 문제를 보면 알겠지만 보통 union find가 중요한게 아니다

MST를 만드는데 간선이 N^2개 있는 골때리는 문제 

-> 간선의 후보를 잘 줄여보자.

 

#23034 조별과제 멈춰!

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

마찬가지로 MST를 만드는데 간선이 M개이니 O(MQ) = O(1e9)으로 TLE가 난다

-> 간선의 후보를 잘 줄여보자

 

#20531 인간관계

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

수학을 곁들여 드셔보시겠습니까?

결국에는 남은 '학생 그룹'의 수가 중요하다는 것을 깨달을 수 있다.

익숙한 느낌으로는 (사실 똑같음) 제 2종 스털링 수가 있는데 그런거 몰라도 풀 수 있다.

참고로 이 점화식 값을 그대로 때려박은 O(1) 풀이가 있다.

 

#3830 교수님은 기다리지 않는다

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

일단 테케 개수 없고 쿼리에 !? 꼬라지부터 비호감 그 자체인데 2012 문제이니까 넘어가자.

무게 차이를 구할 수 있는지 없는지를 알아내는 것은 그냥 union find그 자체이다.

이제 merge에서 무언가를 하는 것이 아니라 find에서 무언가를 하면 된다.

find에서 x와 x 그룹 대표와의 관계를 항상 갱신해주면 된다.

union find가 복잡도를 보장해주기 때문에 find에서 O(lgn) 미만이면 보통 뭘해도 착하게 봐준다.

 

#16213 dgeu-learning

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

단순히 x, y의 관계를 보는 것이 아니라 x와 y사이의 경로를 찾아보자!

소개하려는 풀이는 제일 마지막 4번 풀이이다. 참고로 1, 2, 3번은 +a의 지식 수준을 요구한다.

1) 따분한 풀이 (HLD)

-> MST를 만들어내고 (정확히 말하면 Maximum spanning tree) HLD를 통해서 쿼리를 뚫는다.

2) 출제자의 의도 풀이 (PBS)

-> pbs를 하여 어떤 값 이하로 풀 수 있는지 확인해주면 된다. (크루스칼의 공)

3) 내가 푼 풀이 (작은거에서 큰거로 합치는 테크닉)

-> 거의 모든 MST틱한 문제들이 그렇듯이 간선들을 모두 정렬해 두고 큰거부터 합치기 시작할 것이다.

-> Query(u, v)가 있다면 이 값은 u와 v가 처음으로 같은 그룹에 포함하게 해준 간선의 무게이다.

-> 따라서 만일 u, v가 묶이기 전에 p[u] = w와 같은 일이 일어나더라도 Query(u, v) = Query(w, v)로 넘길 수 있다.

-> 따라서 모든 컴퓨터가 자신과 관련된 모든 쿼리들을 들고 있다가 대표가 바뀌면 걔한테 던져버리면 된다.

-> 그러다가 a가 (a, b) 쿼리를 가지고 있을 때 b와 합쳐지면 그때서야 그 쿼리 값을 저장하면 된다.

-> 총 쿼리의 개수는 Q개 이므로 작은거에서 큰 것으로 합치는 테크닉을 이용하면 넘기는 작업이 QlgQ로 시간 내

-> 사실 나는 set으로 이 쿼리들을 관리해서 lg가 하나 더 붙는데 1초 내로 통과했으니 됐지 뭐

 

4) 흥미로운 풀이 

https://www.acmicpc.net/source/22841064  (AC를 받아야만 볼 수 있음)

처음보면 i) 이게 왜 되는거지? ii) 복잡도가 어떻게 되는거지? 의 의문을 가진다.

i) 이게 왜 되는가 :

-> 이문제에서는 경로압축을 하지 않기 때문에 w[x]는 단순하게 x와 p[x] 사이의 거리이다.

-> 그렇다면 답을 구하는 while문은 union find가 이루어지는 그래프 상에서 u에서 v까지의 경로상 최솟값이다.

-> 이문제에서의 답은 union find로 만들어지는 그래프에서의 경로에서의 값과 동일하기 때문에 된다.

ii) 의심스러운 while 문이 시간 내에 돌아가는가

-> 경로압축을 하지 않았을 때에도 union find가 가능하다는 것을 생각해보면 당연히 시간 내에 된다.

 

#11991 Fenced in (Platinum)

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

대충 nm개의 공간을 4nm개 정도의 간선을 고려하며 합치는 것은 말이 안된다.

그렇다고 nm개가 아니라 1e8개 정도의 간선만으로 합칠 수 있는 것도 아니다.

반복되는 행위가 많기 때문에 간단하게 정리시킬 수 있다. 실제로는 n + m번 정도만 계싼하면 된다.

풀이는 금방 떠오르는데 정확하게 정리하는데 시간이 좀 걸렸다.

 

#13361 최고의 대장장이 토르비욘

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

반드시 너비가 줄어야 함 + 모든 판을 사용해야 함 이라는 조건 때문에 이상해진다.

사실상 N개를 모두 쓰는 상황을 만들어주기만 하면 된다.

-> N개를 모두 쓸 수 있는 조건이 뭐인가요

-> 변길이가 s, t라면 s-t edge를 모두 만들었을 때 E-V <= 1 이되어야 한다.

-> 일단 이 그래프 만들기만 한다면 최대한 검이 길어지도록 고르는 것은 어렵지 않다.