[LeetCode#1631] Path With Minimum Effort

 

❐ Description

---

[1631. Path With Minimum Effort] 문제를 다시 풀었는데 제대로 풀지 못해서 정리한다.

 

 

 

 

 

❐ 접근 방식 (Binary Search)

---

여기서는 Mid 값일 때 움직일 수 있는 경로만 움직이는 것이 핵심 포인트다.

 

1. lowerEffort, upperEffort를 각각 설정한다.
   • 최소 : 0
   • 최대 : 1_000_000
2. lowerEffort가 upperEffort 보다 작을 때만 while문을 수행한다.
   • 시작점으로 부터 좌,우,위,아래를 순회하는데
   • Mid 값보다 작거나 같은 경우에만 이동할수 있다.
3. 목표 지점에 도달했는지 확인한다.
   
   • 도달하지 못함 ⇨ 현재 Mid 값으로 부족 ⇨ 더 큰 Mid 값이 필요 ⇨ lower = mid;
   • 도달 함 ⇨ 현재 Mid 값으로도 충분 ⇨ 최소 Mid를 찾을 필요 있음 ⇨ upper = mid - 1;

 

🤔 왜 `lowerEffort < upperEffort`, `upperEffort = mid` 일까? ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

while (lowerEffort < upperEffort) {
    //...
    if (visited[row][col]) {
        upperEffort = mid - 1;
    } else {
        lowerEffort = mid + 1;
    }
}

위와 같이 코드를 작성하게 되면 아주 치명적인 문제가 발생하는데, 그건 바로 답이 될 수 있는 Mid 값이

누락될 수 있다는 것이다. 따라서 이진 탐색에서 답이 될 가능성이 있는 범위(mid)를 제외하지 않고 유지

해야 한다. 따라서 이 코드에서는 upperEffort = mid를 사용해야 한다.

 

 

 

 

 

❐ Solution

---

public class SolutionV2 {
    private boolean[][] visited;
    private final int[][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    private int maxRow, maxCol;

    public int minimumEffortPath(int[][] heights) {
        maxRow = heights.length;
        maxCol = heights[0].length;

        visited = new boolean[maxRow][maxCol];

        int lowerLimit = 0, upperLimit = 1_000_000;

        while (lowerLimit < upperLimit) {
            int mid = (upperLimit + lowerLimit) / 2;
            for (boolean[] row : visited) Arrays.fill(row, false);

            dfs(0, 0, mid, heights);

            if (visited[maxRow - 1][maxCol - 1])
                upperLimit = mid;
            else
                lowerLimit = mid + 1;
        }

        return lowerLimit;
    }

    private void dfs(int row, int col, int limitEffort, int[][] heights) {
        if (visited[row][col]) return;
        visited[row][col] = true;

        if (row == maxRow - 1 && col == maxCol - 1) return;

        for (int[] dir : dirs) {
            int nextRow = row + dir[0];
            int nextCol = col + dir[1];

            if (nextRow < 0 || nextRow >= maxRow || nextCol < 0 || nextCol >= maxCol) continue;

            int newEffort = Math.abs(heights[row][col] - heights[nextRow][nextCol]);
            if (newEffort <= limitEffort) {
                dfs(nextRow, nextCol, limitEffort, heights);
            }
        }
    }
}

 

 

 

 

 

---