You are a hiker preparing for an upcoming hike. You are given
heights
, a 2D array of size rows x columns
, where heights[row][col]
represents the height of cell (row, col)
. You are situated in the top-left cell, (0, 0)
, and you hope to travel to the bottom-right cell, (rows-1, columns-1)
(i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.
Return the minimum effort required to travel from the top-left cell to the bottom-right cell.
Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]] Output: 2 Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells. This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]] Output: 1 Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].
Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]] Output: 0 Explanation: This route does not require any effort.
Constraints:
rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10
6
풀이
재영
- bfs로 풀려고 시도했으나 시간초과.
const minimumEffortPath = (heights) => { const queue = []; const start = [0, 0, 0]; const xLength = heights.length; const yLength = heights[0].length; let efforts = Infinity; const dp = Array.from({ length: xLength }, () => Array.from({ length: yLength }, () => [ Infinity, Infinity, Infinity, Infinity, ]) ); const directions = [ [1, 0], [-1, 0], [0, 1], [0, -1], ]; queue.push(start); dp[0][0] = [0, 0, 0, 0]; while (queue.length) { const [x, y, total] = queue.shift(); if (x === xLength - 1 && y === yLength - 1) { efforts = Math.min(efforts, total); continue; } for (let i = 0; i < 4; i += 1) { const [dx, dy] = directions[i]; const nx = x + dx; const ny = y + dy; if (nx >= 0 && ny >= 0 && nx < xLength && ny < yLength) { const nowEffort = Math.max( total, Math.abs(heights[nx][ny] - heights[x][y]) ); if (nowEffort < dp[nx][ny][i]) { dp[nx][ny][i] = nowEffort; queue.push([nx, ny, nowEffort]); } } } } return efforts; };
해결 - minHeap + bfs 적용
class MinHeap { constructor() { this.heap = [null]; } heappush(val) { this.heap.push(val); let nowIndex = this.heap.length - 1; let parentIndex = this.getParentIndex(nowIndex); while (nowIndex > 1 && this.heap[nowIndex][1] < this.heap[parentIndex][1]) { this.swap(nowIndex, parentIndex); nowIndex = parentIndex; parentIndex = this.getParentIndex(nowIndex); } } heappop() { if (this.heap.length === 1) return; if (this.heap.length === 2) return this.heap.pop(); const min = this.heap[1]; this.heap[1] = this.heap.pop(); let [nowIndex, leftIndex, rightIndex] = this.getUpdatedindices(1); if (leftIndex > this.heap.length - 1) { return min; } if ( rightIndex > this.heap.length - 1 && this.heap[leftIndex][1] < this.heap[nowIndex][1] ) { this.swap(nowIndex, leftIndex); return min; } while ( leftIndex < this.heap.length - 1 && rightIndex < this.heap.length && (this.heap[leftIndex][1] < this.heap[nowIndex][1] || this.heap[nowIndex][1] < this.heap[leftIndex][1]) ) { const minIndex = this.heap[rightIndex][1] < this.heap[leftIndex][1] ? leftIndex : rightIndex; this.swap(minIndex, nowIndex); [nowIndex, leftIndex, rightIndex] = this.getUpdatedindices(minIndex); } return min; } getParentIndex(index) { return Math.floor(index / 2); } getUpdatedindices(index) { return [index, index * 2, index * 2 + 1]; } swap(a, b) { [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]]; } } const minimumEffortPath = (heights) => { const minHeap = new MinHeap(); const xLength = heights.length; const yLength = heights[0].length; const directions = [ [1, 0], [-1, 0], [0, 1], [0, -1], ]; const dp = []; for (let i = 0; i < xLength; i += 1) { dp.push(JSON.parse(JSON.stringify(new Array(yLength).fill(1000000)))); } dp[0][0] = 0; minHeap.heappush([0, 0, 0]); while (minHeap.heap.length > 1) { const [x, y, effort] = minHeap.heappop(); for (let i = 0; i < 4; i += 1) { const [dx, dy] = directions[i]; const nx = x + dx; const ny = y + dy; if (nx >= 0 && nx < xLength && ny >= 0 && ny < yLength) { const nowEffort = Math.abs(heights[nx][ny] - heights[x][y]); const nextEffort = Math.max(effort, nowEffort); if (dp[nx][ny] > nextEffort) { dp[nx][ny] = nextEffort; minHeap.heappush([nx, ny, nextEffort]); } } } } return dp[xLength - 1][yLength - 1]; };
은찬
class PriorityQueue { constructor(){ this.queue = [0]; this.size = 0; } push(value) { this.queue.push(value); this.size++; this.moveUp(this.size); } moveUp(index){ while(Math.floor(index / 2)){ const parent = Math.floor(index / 2); if(this.queue[parent][2] > this.queue[index][2]){ const tmp = this.queue[index]; this.queue[index] = this.queue[parent]; this.queue[parent] = tmp; } index = parent; } } pop() { const minValue = this.queue[1]; this.queue[1] = this.queue[this.size]; this.queue.pop(); this.size--; this.moveDown(1); return minValue; } moveDown(index) { while(index * 2 <= this.size){ const minChildIndex = this.findMinChildIndex(index); if(this.queue[index][2] > this.queue[minChildIndex][2]){ const tmp = this.queue[minChildIndex]; this.queue[minChildIndex] = this.queue[index]; this.queue[index] = tmp; } index = minChildIndex; } } findMinChildIndex(index) { const left = index * 2; const right = (index * 2) + 1; if(right > this.size){ return left; } else{ if(this.queue[right][2] < this.queue[left][2]){ return right; } else{ return left; } } } } const minimumEffortPath = (heights) => { const row = heights.length; const column = heights[0].length; const directX = [-1, 1, 0, 0]; const directY = [0, 0, -1, 1]; const visited = Array.from({length: row}, () => Array(column).fill(false)); const pq = new PriorityQueue(); pq.push([0, 0, 0]); while(pq.size){ const [x, y, effort] = pq.pop(); if(x === row - 1 && y === column - 1){ return effort; } visited[x][y] = true; for(let i = 0; i < 4; i++){ const nx = x + directX[i]; const ny = y + directY[i]; if(nx >= 0 && nx < row && ny >= 0 && ny < column && !visited[nx][ny]){ const newEffort = Math.abs(heights[x][y] - heights[nx][ny]); pq.push([nx, ny, Math.max(effort, newEffort)]); } } } return -1; };