솔루션: 최소한의 노력으로 경로

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #1631(중간): 최소 노력의 경로

설명:

당신은 다가오는 하이킹을 준비하는 등산객입니다. 크기가 heights 인 2D 배열인 rows x columns 가 주어집니다. 여기서 heights[row][col] 는 셀(row, col) 의 높이를 나타냅니다. 왼쪽 상단 셀(0, 0)에 있으며 오른쪽 하단 셀(rows-1, columns-1)(즉, 인덱스 0)로 이동하려고 합니다. 위, 아래, 왼쪽 또는 오른쪽으로 이동할 수 있으며 최소한의 노력이 필요한 경로를 찾고자 합니다.

경로의 노력은 경로의 연속된 두 셀 사이의 높이의 최대 절대 차이입니다.

왼쪽 상단 셀에서 오른쪽 하단 셀로 이동하는 데 필요한 최소 노력을 반환합니다.


예:


예 1:



입력:
높이 = [[1,2,2],[3,8,2],[5,3,5]]

산출:
2

설명:
[1,3,5,3,5]의 경로는 연속 셀에서 최대 절대 차이가 2입니다. 이것은 최대 절대 차이가 3인 [1,2,2,2,5]의 경로보다 낫습니다. .

비주얼:




예 2:



입력:
높이 = [[1,2,3],[3,8,4],[5,3,5]]

산출:
1

설명:
[1,2,3,4,5]의 경로는 연속 셀에서 최대 절대 차이가 1이므로 경로 [1,3,5,3,5]보다 낫습니다.

비주얼:




예 3:



입력:
높이 = [[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]]

산출:
0

설명:
이 경로는 노력이 필요하지 않습니다.

비주얼:




제약:

행 == 높이.길이

열 == 높이[i].길이

1 <= 행, 열 <= 100

1 <= 높이[i][j] <= 10^6

아이디어:

높이의 셀을 그래프의 노드로 생각하고 셀에서 이웃으로 이동하는 노력을 두 노드를 연결하는 가장자리의 가중치로 생각하면 BFS 접근 방식을 사용할 수 있습니다. 해결책.

가장자리는 가중치가 있는 것으로 간주되어야 하므로 약간 수정된 Dijkstra의 알고리즘을 사용하여 최소한의 노력으로 경로를 찾을 수 있습니다. Dijkstra의 알고리즘에서 평소와 같이 이동 목록을 보관할 최소 힙 저장소를 구현해야 합니다.

Dijkstra의 알고리즘은 기본적으로 표준 그래프 BFS 접근 방식처럼 작동합니다. 단, 다음 노드에 도달하는 속도(또는 이 경우에는 노력이 거의 없음)에 따라 우선 순위를 정합니다. 그렇게 하기 위해 우리는 어떤 노드가 이미 방문했는지(vis) 추적하고 시작점에서 최소한의 누적 노력으로 도달할 수 있는 가능한 노드를 기반으로 다음 노드의 우선 순위를 지정하는 방법을 사용하면 됩니다. .

효율성을 더욱 높이기 위해 각 노드에서 찾은 최선의 노력을 추적하고 더 나쁜 경로가 힙에 입력되지 않도록 방지할 수 있습니다.


구현:

자바스크립트에서는 0 또는 1만 포함하므로 vis에 Uint8Array를 사용할 수 있습니다. 마찬가지로 1에서 1e6까지의 정수만 포함하므로 노력을 위해 Uint32Array를 사용할 수 있습니다.

또한 MinPriorityQueue()가 있는 코드 버전도 포함시켰습니다. 이 코드는 우리를 위해 min-heap 작업을 수행하지만 특수 제작된 min-heap보다 훨씬 덜 효율적입니다.


최소 힙이 포함된 Javascript 코드:

var minimumEffortPath = function(H) {
    let y = H.length, x = H[0].length, last = x*y-1,
        vis = new Uint8Array(last+1),
        effort = new Uint32Array(last+1).fill(1000001), 
        heap = [,], node = 0, path = 0, i, j, cell

    const heapify = (next, k, l) => {
        let newEff = Math.max(path, Math.abs(cell - H[k][l]))
        if (effort[next] <= newEff) return
        effort[next] = newEff
        let i = heap.length, par = i >> 1
        heap.push([next,newEff])
        while (par && heap[par][1] > heap[i][1]) {
            [heap[par], heap[i]] = [heap[i], heap[par]]
            i = par, par = i >> 1
        }
    }

    const extract = () => {
        let min = heap[1], left, right,
            i = 1, child = heap[3] && heap[3][1] < heap[2][1] ? 3 : 2
        heap[1] = heap.pop()
        while (heap[child] && heap[i][1] > heap[child][1]) {
            [heap[i], heap[child]] = [heap[child], heap[i]]
            i = child, left = i << 1, right = left + 1
            child = heap[right] && heap[right][1] < heap[left][1] ? right : left
        }
        return min
    }

     while (node !== last) {
        i = ~~(node / x), j = node % x, cell = H[i][j]
        if (i > 0 && !vis[node-x]) heapify(node-x, i-1, j)
        if (i < y-1 && !vis[node+x]) heapify(node+x, i+1, j)
        if (j > 0 && !vis[node-1]) heapify(node-1, i, j-1)
        if (j < x-1 && !vis[node+1]) heapify(node+1, i, j+1)
        vis[node] = 1
        while (vis[node]) [node,path] = extract()
    }
    return path
};

MinPriorityQueue()가 포함된 자바스크립트 코드:

이 코드는 덜 효율적이지만 읽기 쉽습니다. leetcode가 기본적으로 javascript 구현에서 활성화한 priorityqueue npm 패키지를 사용합니다.

var minimumEffortPath = function(H) {
    let y = H.length, x = H[0].length,
        vis = new Uint8Array(x*y),
        effort = new Uint32Array(x*y).fill(1000001), 
        node = 0, path = 0, i, j, cell,
        pq = new MinPriorityQueue({priority: x => x[1]})

    const insert = (next, k, l) => {
        let newEff = Math.max(path, Math.abs(cell - H[k][l]))
        if (effort[next] <= newEff) return
        effort[next] = newEff
        pq.enqueue([next, effort[next]])
    }

    while (node !== x*y-1) {
        i = ~~(node / x), j = node % x, cell = H[i][j]
        if (i > 0 && !vis[node-x]) insert(node-x, i-1, j)
        if (i < y-1 && !vis[node+x]) insert(node+x, i+1, j)
        if (j > 0 && !vis[node-1]) insert(node-1, i, j-1)
        if (j < x-1 && !vis[node+1]) insert(node+1, i, j+1)
        vis[node] = 1
        while (vis[node]) [node, path] = pq.dequeue().element
    }
    return path
};