1631. Path With Minimum Effort

[zeikar]

Problem link

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

Problem Summary

경로상의 좌표의 절댓값 차이가 최소가 되도록 경로를 찾는 문제.

Solution

딱 보고 pq로 BFS 돌렸는데 시간 초과. 아마 같은 좌표가 여러 번 들어가서 큐가 잔뜩 쌓이지 않았나 싶다. 그래서 다익스트라로 변경.
다익스트라가 pq 기반 BFS와 큰 차이는 없는데 distances 배열을 둬서 다음 값이 더 크다면 방문을 스킵하는 방식으로 동작한다.

Source Code

import heapq
from typing import List


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        rows = len(heights)
        cols = len(heights[0])
        queue = [(0, 0, 0)]
        distances = [[9999999] * 100 for i in range(100)]

        direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        while queue:
            e, x, y = heapq.heappop(queue)

            if x == rows - 1 and y == cols - 1:
                return e

            for d in direction:
                nx, ny = x + d[0], y + d[1]

                if nx < 0 or nx >= rows or ny < 0 or ny >= cols:
                    continue

                diff = max(e, abs(heights[x][y] - heights[nx][ny]))

                if distances[nx][ny] > diff:
                    distances[nx][ny] = diff
                    heapq.heappush(queue, (diff, nx, ny))

        return -1