Algorithm problem-25

1. 문제

• M x N 의 matrix에서 시작점에서 목표까지의 최소 이동시간을 리턴하라
• 1은 장애물, 0은 이동 가능한 통로를 의미
• 로봇은 1분에 한칸씩 이동할 수 있음

2. 시도

• 이동할 수 있는 경우의 수를 구하고
• 모든 경우의 수를 이동하며, 카운팅한 값을 결과 배열에 저장하고
• 그 중 가장 작은 값을 리턴하는 식으로 구상하였음
• 문제를 이해하고, 위의 방식으로 수도코드를 구현하다가 해결방법에서 멀어진다고 느끼고
• 다른 방향을 고민하다가 시간 초과하였음
• 지뢰 찾기 게임과 비슷한 방식으로 문제를 해결해보자
• 최초에, 주어진 매트릭스에서 1로 표시한 장애물 값을 임의의 텍스트로 교체하고
• 시작점에서 멀어질 때마다 위치의 값을 이전 값 + 1로 바꾸는 식으로 전체 배열의 0 값을 바꾸고
• 바꾸는 도중 0이 아닌 값과 마주치면 바꿀 값과 현재의 값 중 작은 값으로 변경
• 모든 배열을 다 바꾼 후 도착 지점의 결과 값을 리턴하는 식으로 구현해보자
• 아래까지 짜보고, 방법이 잘못되었음을 깨닫고 결국 레퍼런스를 보고 이해하기로 하였음

3. 시도

const robotPath = function (room, src, dst) {
  // room에 위치한 1의 값을 임의의 텍스트 값('')으로 교체
  for (let i = 0; i < room.length; i++) {
    for (let j = 0; j < room[i].length; j++) {
      if (room[i][j] === 1) {
        room[i][j] = '';
      }
    }
  }
  // src의 값을 's'로 변경
  let [r,c] = src;
  room[r][c] = 's';
  // 모든 배열의 값이 0이 아닐때까지 변경, 그러기 위한 배열의 0의 수를 카운트 하는 함수를 작성
  let cnt = 0;
  // 시작점에서 출발하며 상하좌우의 위치가 유효하다면, 값을 +1씩 바꾼다
};

4. 레퍼런스

const robotPath = function (room, src, dst) {
  // 현재 위치를 중심으로 4방향의 값을 현재값 +1로 바꿔주는 함수를 구현하자
  const stepper = (m, n, now, step) => {
    // 현재 위치를 좌표값으로 옮겨 담는다
    const [r, c] = now;
    // 배열의 범위를 벗어난 경우
    if (r < 0 || r >= m || c < 0 || c >= n) return;
    // 0이거나, 현재 스탭보다 값이 크다면, 현재 스탭값으로 변경시킨다
    if (room[r][c] === 0 || room[r][c] > step) {room[r][c] = step;}
    // 그 외, 장애물(1)이거나, 현재 스탭보다 작은(최소 시간으로 통과한) 경우
    else {return;}
    // 4방향을 탐색, dfs로 진행한다, 완전탐색을 진행하므로 bfs도 큰 차이는 없지만
    // 도착지에 최소값으로 도달한 경우 종료되게 코드를 작성할 수 있으면 약간 더 효율적임
    // 아래의 경우를 재귀하여 탐색하게 되면, 범위 내의 모든 값을 최대 4회씩 퍼져 나가면서 탐색하게 됨
    // 종료 시점은 모든 범위 내에서 4회의 시도를 한 경우가 될 것이고, 범위 밖에서는 진행이 되지 않으므로
    // 자동적으로 종료가 된다
    stepper(m, n, [r + 1, c], step + 1);
    stepper(m, n, [r - 1, c], step + 1);
    stepper(m, n, [r, c + 1], step + 1);
    stepper(m, n, [r, c - 1], step + 1);
  };
  // 현재 위치의 값을 1로 시작해야 시작점으로 되돌아오지 않는다
  // 계산이 완료된 후에, 도착지점의 값에서 -1을 해주면 올바른 값이 된다
  stepper(room.length, room[0].length, src, 1);
  const [row, col] = dst;
  return room[row][col] - 1;
}