[leetcode][778] Swim in Rising Water]

문제 : https://leetcode.com/problems/swim-in-rising-water/

---

N x N 배열 grid가 입력으로 주어진다. grid[i][j] = (i,j) 위치의 높이.

시간 t에서 모든 grid 위치의 수심은 t이고, 인접한 위치의 고도가 t 이하인 경우에만 이동가능하다.

이동하는데 드는 시간은 고려하지 않는다. grid의 (0,0)에서 (N-1, N-1)로 이동할 때 도달할 수 있는 최소시간은 얼마인가

---

이동하는데 드는 시간은 고려하지 않으므로 결국 (0, 0) -> (N-1, N-1)로 이동하는 경로의 고도값들의 최대값의 최소값을 구하는 문제이다.

다익스트라로 풀었다.

간선의 가중치는 u -> v로 이동한다고 했을 때, v 위치의 높이가 된다.

즉, 높이가 낮은 인접한 위치로 이동하면서 (N-1, N-1)로 이동한다.

이동 중 높이의 최대값을 구하면 (N-1, N-1)로 도착했을 때 해당 값이 정답이 된다.

 

시간복잡도는 O(N^2 log(N^2)). 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/778.%20Swim%20in%20Rising%20Water.cpp