알고리즘 | leet code | Path With Minimum Effort (BFS)

📌 문제 : 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

 

접근 방식 

BFS를 사용하였다. 입력 1을 기준으로 설명하겠다.

 

초기 설정

dist 배열에는 현재 위치에 오기 까지의 가장 최소의 노력이 저장된다.

따라서 dist[0][0]은 현재 나의 위치니 0이 저장된다.

나머지 칸에는 아직 최소의 노력을 계산하여 저장하지 않았으므로, MAX_SAFE_INTEGER을 넣어놓는다.

dx, dy는 4가지 방향으로 이동하면서 최소의 노력을 계산할 것이기 때문에 미리 이동할 경우를 저장해놓았다.

 

queue에 다음에 이동할 위치를 저장한다.

현재 위치 [0, 0] 부터 시작할 것이므로 미리 queue에 넣어둔다.

 

BFS

queue의 길이가 0이 되기 전까지 최소 노력 계산을 반복한다.

현재 위치를 queue에서 shift하여 curx, cury에 저장한다.

 

for문으로 사방을 순회하며 최소 노력을 계산한다.

현재에서 다음으로 이동할 위치를 nx, ny에 저장한다.

 

만약 등산을 할 수 있는 2차원 배열의 범위를 벗어나면 그만 탐색해야하므로, 

if문의 조건으로 배열의 범위안에 nx, ny가 존재하는지 확인한다.

만약 범위안에 들어온다면 이제 최소 노력을 계산한다.

 

최소 노력은 다음 두 개중 큰 것으로 결정된다.

현재 위치에서 최소 노력(dist[curx][cury]),

현재 위치 높이와 다음 위치 높이의 차이(Math.abs(heights[nx][ny] - heights[curx][cury])

 

따라서 minEffort 에 최소 노력을 저장한 다음, 다음 위치의 최소 노력 (dist[nx][ny])와 비교한다.

처음에 dist에 값들을 MAX_SAFE_INTEGER을 넣어놨으므로 

현재 계산된 minEffort가 다음 위치 최소 노력 보다 작다면, 다음 위치의 최소 노력이 갱신된다.

이후에 계속 계산을 진행하면서, 다시 계산된 minEffort값이 이전에 계산된 최소 노력보다 더 작다면 갱신해주게 된다.

 

그 다음 다음 위치에서 사방으로 탐색을 진행하기 위해 nx, ny를 queue에 삽입한다. 

 

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 dist = Array.from({ length: n }, () => Array(m).fill(Number.MAX_SAFE_INTEGER));

    function BFS() {
      let queue = [[0, 0]];
      dist[0][0] = 0;
      while (queue.length) {
        let [curx, cury] = queue.shift();
        for (let i = 0; i < 4; i++) {
          let [nx, ny] = [curx + dx[i], cury + dy[i]];

          if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
            let minEffort = Math.max(Math.abs(heights[nx][ny] - heights[curx][cury]), dist[curx][cury]);
            if (dist[nx][ny] > minEffort) {
              dist[nx][ny] = minEffort;
              queue.push([nx, ny]);
            }
          }
        }
      }
    }
    BFS();
    console.log(dist);
    return dist[n - 1][m - 1];
  }