알고리즘 토이 25

const robotPath = function (room, src, dst) {
  const aux = (M, N, candi, step) => {
    // 현재 위치
    const [row, col] = candi;

    // 배열의 범위를 벗어난 경우
    if (row < 0 || row >= M || col < 0 || col >= N) return;

    if (room[row][col] === 0 || room[row][col] > step) {
      room[row][col] = step;
    } else {
      // 장애물(1)이거나 이미 최소 시간(1)으로 통과가 가능한 경우
      return;
    }

    // dfs로 4가지 방향에 대해 탐색을 한다.
    // 완전탐색을 해야하므로 bfs나 dfs가 큰 차이가 없다.
    // bfs의 경우 목적지에 도착하는 경우 탐색을 중단해도 되므로,
    // 약간 더 효율적이다.
    aux(M, N, [row + 1, col], step + 1); // 상
    aux(M, N, [row - 1, col], step + 1); // 하
    aux(M, N, [row, col - 1], step + 1); // 좌
    aux(M, N, [row, col + 1], step + 1); // 우
  };

  // 로봇이 서 있는 위치를 1로 초기화하면 (다시 방문하지 않기 위해서),
  // 바로 옆 통로는 2가 된다.
  // 계산이 완료된 후에 최종값에 1을 빼주면 된다.
  aux(room.length, room[0].length, src, 1);

  const [r, c] = dst;
  return room[r][c] - 1;
};

{/* 

세로와 가로의 길이가 가각 M,N인 방의 지도가 2차원 배열로 주어졌을대, 1은 장애물을 의미하고 0 이동이가능한 통로를 의미.
로봇은 지도 위를 일분에 한칸씩 좌우로 이동할수있음. 로봇의 위치가 와 목표지점이 함께 주어질 경우, 로봇이 목표지점까지 도달하는데 걸리는 최소시간을 리턴해야합니다.

룸은 보드

src 좌표에서  dst로 가는 좌표로 가는게 최소한의 리턴인가?


 */}

최단 거리 dps 완전탐색 방법이다 각 좌표마다 4갈래길이 존재하며 우선 좌표함수를 실행시켰을시에 0인좌표가나왔을시
1을 추가해가며 이동을한다 그렇게 쭉이동을하고 다마쳤을때 가지않았던방향으로 다시 스택배출이 되면서
좌표당 가지 않았던 방향을 탐색하게 되고 거기서 또 0이있거나 아니면 지금 내가 찍은 스텝보다 큰게있거나 0이있다면

현재 스텝을 할당을 해준다 왜냐하면 이쪽길로는 오지않았을수도 있기때문이다 또 그방향에서 탐색을 하게 된후

좌표당 잠표함수가 전부 실행이됬다면 스택 배출이 되간다.. 전부 그런식으로 탐색을하고

결국엔 이 문제와 입출력 예시에서는 출발지점에서는 우로가는길을 가본적이없고 그당시 step이 거의 초기 스텝이기때문에

그리고 오른쪽에 있는 좌표는 뻉둘러서 한번 가서 18정도에 스택이 찍혀있다 이걸 현재의 스텝으로 바꿔주면서 다시 쭉쭉 탐색해나가고

좌표함수가 전부 실행된 좌표는 환수실행환료했으니 스택배출 안가본곳이나 스텝이 더큰곳은 다시 재할당하면서 전부 탐색을해주고

더이상 탐색할게 없을시에 마무리로 내가 원하는 지점의 스텝에서 -1을 빼준다 왜냐면 메트릭스가 0부터 시작하기때문이다

그러면 완성!