[LeetCode] 1631 | Path With Minimum Effort | Python

---

문제 링크: https://leetcode.com/problems/path-with-minimum-effort/

---

문제

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.

---

조건

• rows == heights.length
• columns == heights[i].length
• 1 <= rows, columns <= 100
• 1 <= heights[i][j] <= $10^6$

---

내 풀이

이렇게 알고리즘을 어떻게 짜야하지?라는 생각이 드는 문제는 대부분 이분탐색이나 DP다.

이번에는 이분탐색으로 풀었다.

 

DFS로 탐색을 진행하며, 경로가 겹치지 않게 하기 위해 self.visited를 이용했다.

그리고 현재 low와 high로 정해진 mid보다 격차가 작은 타일로만 이동해서 최종 목적지에 도달할 수 있는지를 파악한다.

---

코드

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        self.heights = heights
        self.H, self.W = len(heights), len(heights[0])
        left, right = 0, 1000001
        
        while left < right:
            mid = (left + right) // 2
            
            self.visited = set()
            if self.dfs(0, 0, mid):
                right = mid
            else:
                left = mid + 1
        
        return left
    
    
    def dfs(self, y, x, mid):
        if (y, x) == (self.H-1, self.W-1):
            return True
        
        self.visited.add((y, x))
        for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            newY, newX = y+dy, x+dx
            if 0 <= newY < self.H and 0 <= newX < self.W and (newY, newX) not in self.visited and\
                                        abs(self.heights[y][x]-self.heights[newY][newX]) <= mid:
                if self.dfs(newY, newX, mid):
                    return True
        
        return False