BOJ 16074: Mountaineers

Link

• https://www.acmicpc.net/problem/16074

• GCPC 2018 M번

Tag

• PBS

Time Complexity

• $O((N+Q)lgN)$

가중치가 있는 $N \times M$ 그리드가 있고, $(x1, y1)$ 와 $(x2, y2)$ 를 잇는 경로의 가중치의 최댓값의 최솟값을 묻는 쿼리가 Q개 주어진다. 쿼리 하나를 이분탐색으로 처리한다고 생각해보면, '가중치가 $k$ 이하인 정점들만 가지고 $(x1, y1)$ 와 $(x2, y2)$ 를 연결할 수 있는가?' 가 결정문제가 되고, 이는 Union-Find 를 이용해주면 된다. Q개의 쿼리를 처리하려면, 가중치가 작은 정점부터 보면서 추가하고 해당 mid값을 가진 쿼리에 대해 답해주면 된다.

 PBS 연습문제.

Code