알고리즘 | leet code | Path With Minimum Effort (DFS + 이분탐색)

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

 

문제

당신은 다가오는 하이킹을 준비하는 등산객입니다.
heights[row][col]은 셀(row, col)의 높이를 나타내는 행 x 열 크기의 2D 배열 높이가 제공됩니다.
당신은 왼쪽 상단 셀 (0, 0)에 있고 오른쪽 하단 셀 (행-1, 열-1)(즉, 0 인덱스)로 이동하기를 원합니다.
위, 아래, 왼쪽 또는 오른쪽으로 이동할 수 있으며 최소한의 노력이 필요한 경로를 찾고 싶습니다.
경로의 노력은 경로의 연속된 두 셀 사이의 최대 절대 높이 차이입니다.
왼쪽 상단 셀에서 오른쪽 하단 셀로 이동하는 데 필요한 최소 노력을 반환합니다.

✔️입력1
heights = [[1,2,2],[3,8,2],[5,3,5]]
✔️출력1
2

 

접근 방식 

DFS + 이분탐색 

답이 될 수 있는 값은 0~10^6 사이이므로 이분탐색으로 돌면서 정답이 되는지 확인한다.

정답이 되는지 확인하는 함수는 DFS로 heights를 탐색하면서 

현재 위치와 다음 위치의 높이 차가 mid보다 작거나 같으면 정답이 될 수 있고,

정답이 될 수 있다면 다음 위치로 DFS를 돌려서 그것도 정답이 될 수 있는지 확인한다.

종점에 닿으면 도착한 것이므로 true를 반환하여 스택에 쌓여있던 함수들이 깨어나며 계속 true를 반환하게 되고

최종적으로 true를 반환하고 종료한다.

 

만약 현재 위치와 다음 위치의 높이 차라 mid보다 크거나, 다음 위치는 heights범위에 포함되지 않는다면 탐색을 종료하고

false를 반환하게된다.

 

JavaScript 코드

  function minimumEffortPath(heights) {
    let n = heights.length;
    let m = heights[0].length;
    let dx = [1, -1, 0, 0];
    let dy = [0, 0, 1, -1];
    let lt = 0,
      rt = 1000000;
    let answer = Number.MAX_SAFE_INTEGER;

    // 0,0 에서 시작해서 높이 차가 mid보다 작다면 true
    function DFS(mid, x, y, ch) {
      // 마지막 지점에 닿았으면 그만 탐색해
      if (x === n - 1 && y === m - 1) return true;
      else {
        for (let i = 0; i < 4; i++) {
          let nx = x + dx[i];
          let ny = y + dy[i];

          // 범위에 해당한다면
          if (nx >= 0 && nx < n && ny >= 0 && ny < m && ch[nx][ny] === 0) {
            let dh = Math.abs(heights[x][y] - heights[nx][ny]);
            // 높이 차가 정답이 될 범위에 존재한다면 true
            if (dh <= mid) {
              ch[nx][ny] = 1;
              // 탐색 하면서 mid가 정답이 될 수 있는지 확인한다.
              if (DFS(mid, nx, ny, ch)) return true;
            }
          }
        }
      }
      // for문을 전부 돌았는데도 mid가 정답이 되지 못했다면, false
      return false;
    }

    while (lt <= rt) {
      let mid = Math.floor((lt + rt) / 2);

      let ch = Array.from({ length: n }, () => Array(m).fill(0));
      ch[0][0] = 1;

      if (DFS(mid, 0, 0, ch)) {
        rt = mid - 1;
        answer = Math.min(answer, mid);
      } else {
        lt = mid + 1;
      }
    }
    return answer;
  }