다익스트라2 [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 위치의 높이가 된다. 즉, 높이가 낮은 인접한 위치.. 2021. 6. 21. 다익스트라 알고리즘 (Dijkstra's algorithm) 다익스트라는 최단경로 알고리즘입니다. 하나의 특정 도시에서 다른 도시들로가는 최단경로, 최소비용을 구하는데 사용됩니다. 도시 i에서 j로 가는 비용이 arr[i][j]이고 도시들의 방문여부를 배열 check에 저장, 도시로 가는 최소비용을 배열 dist에 저장한다고 했을 때, 다익스트라 알고리즘은 다음과 같습니다. 1. 현재 도시(now)의 방문 여부를 체크합니다. [check[now] = true] 2. 현재 도시(now)를 거쳐 갈 수 있는 도시(next)들의 비용이 현재 저장되어 있는 비용(dist[next])보다 큰 경우 이를 갱신합니다. [ dist[next] > dist[now] + arr[now][next] => dist[next] = dist[now] + arr[now][next] ] 3... 2019. 9. 18. 이전 1 다음
