Portfolio

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] <= 106

풀이

재영

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;
};

Path With Minimum Effort

풀이

해결 - minHeap + bfs 적용