백준 16074번, Mountaineers 풀이

문제 백준 16074번 풀이 $(x_{1}, y_{1})$에서 $(x_{2}, y_{2})$로 가는 경로에서 방문하는 정점 중 최대 높이를 최소화하여야 합니다. $Q = 1$이라고 가정하면, 높이가 $mid$보다 작은 정점들만 사용하여 $(x_{1}, y_{1})$에서 $(x_{2}, y_{2})$로 가는 경로가 있는가 에 대한 결정 문제를 풀어야 합니다. Union-Find 자료구조를 사용하여 $mid$보다 작은 정점들을 순서대로 합쳐주는 것은 유사 크루스칼 알고리즘을 돌려 결정 문제를 해결할 수 있습니다. 높이 $H$에 대한 이분 탐색 $O(log H)$, 총 정점의 개수가 $MN$이므로 유사 크루스칼 알고리즘을 돌리는데 $O(MNlogMN)$이 걸립니다. 쿼리..

2020.10.25