(Leet Code JS)Path With Minimum Effort

https://leetcode.com/problems/path-with-minimum-effort/

Path With Minimum Effort - LeetCode

 

우선순위큐로를 이용한 풀이.

MinHeap으로 우선순위 큐를 구현.

 

BFS 방식과 비슷하게 PriorityQueue에 방문할 좌표와 minimum effort를 넣으면 된다.

pq에 push하면 알아서 minHeap으로 정렬해주기 때문에 방문할 좌표와 방문 여부를 확인해서 pq에 넣어주면 된다.

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