Algorithm problem-28

1. 문제

• M x N인 지도에 1은 장애물, 0은 통로로 표시됨
• 시작점과 방향, 도착점과 방향이 주어짐
• 방향은 위 1, 오 2, 아 3, 왼 4로 주어짐
• 1턴에 이동 또는 90도 회전 동작을 할 수 있음
• 한방향으로의 직진 이동시에는 1턴으로 전부 이동이 가능함
• 시작점에서 도착점까지의 최소 동작 턴 수를 리턴

2. 시도

• 방향 인자를 추가적으로 고민해야 하는 문제
• 이전에 풀었던 로보패스 문제 풀이를 기초로 변형해보자
• 이전 문제는 이동만 고려해서 생각보다 풀이는 간단했음
• 문제는 방향 전환 루틴, 회전이 한 방향으로만 이루어지는게 아니여서, 회전수가 적게 필요한 방향을 인지하고 그 방향으로 회전시켜야 함
• 처음으로는 상하좌우의 위치값이 범위 내인지, 범위 내라면 장애물인지 통로인지를 파악, 그리고 현재 위치에서 통로로 가는 방향의 값을 파악
• 통로의 값은 위쪽 통로이면 1, 오른쪽 통로이면 2
• 현재의 방향값에 따라 각각의 통로값이 대응하는 회전 값을 미리 계산해놓고 더해주는 방식으로 대응해보면 어떨까
• 현재 1, 상0,우1,하2,좌1
• 현재 2, 상1,우0,하1,좌2
• 현재 3, 상2,우1,하0,좌1
• 현재 4, 상1,우2,하1,좌0
• 위와 같은 대응 값을 갖는다
• 시작점을 1로 바꾸고 시작, 상하좌우의 값을 체크하면서 변경시켜가자
• 지도의 좌표값을 전부 변경시킨 후 도착 좌표의 값을 리턴하면 될 듯, 혹은 -1한 값을 해야할 수도 있겠음
• 문제의 조건 중 1가지를 놓치고 풀이하였음, 직진으로 이동할 때에는 1턴으로 전부 이동이 가능함
• 잘못 이해한 풀이로는 문제가 잘 해결되긴 하였음
• 차후 다시 조건에 맞춰 풀어야 할 것 같음

3. 수도코드

// 문제 이해를 잘못하고 문제를 풀이하였음
// 한 방향의 통로로 직진이동할 때에는 1턴으로 전부 이동하는 조건을 이해 못하고
// 한칸당 1턴으로 이해하고 계산하였음
// 잘못 이해한 문제풀이로는 잘 풀이가 되었음
const robotPath2 = function (room, src, sDir, dst, dDir) {
  // 현재 위치를 중심으로 상하좌우의 값에 대응하여 이동하는데 필요한 턴수를 계산하여 바꿔주는 함수를 작성한다
  // 이동함수는 지도의 범위, 현재좌표, 현재방향, 현재 턴수를 주어야 한다
  const mover = (m, n, now, cur, turn) => {
    // 현재 위치를 좌표값으로 옮겨 놓자
    const [r,c] = now;
    // 배열의 범위를 벗어난 경우는 빈 리턴시키자
    if (r < 0 || r >= m || c < 0 || c >= n) return;
    // 현재 위치값이 0이거나, 현재 턴보다 큰 값을 가지면, 현재 턴 값으로 갱신한다
    if (room[r][c] === 0 || room[r][c] > turn) {room[r][c] = turn;}
    // 장애물이거나, 현재 턴보다 작은 값이면 빈 리턴
    else {return;}
    // cur, 현재방향에 따라 4방향에 주어질 턴의 값이 달라지므로 if로 분기해준다
    // 상 1, 우 2, 하 3, 좌 4
    // 현재 1, 상0,우1,하2,좌1 - 현재 2, 상1,우0,하1,좌2
    // 현재 3, 상2,우1,하0,좌1 - 현재 4, 상1,우2,하1,좌0
    if (cur === 1) {
      mover(m, n, [r - 1, c], 1, turn + 1); // 상
      mover(m, n, [r, c + 1], 2, turn + 2); // 우
      mover(m, n, [r + 1, c], 3, turn + 3); // 하
      mover(m, n, [r, c - 1], 4, turn + 2); // 좌
    }
    if (cur === 2) {
      mover(m, n, [r - 1, c], 1, turn + 2); // 상
      mover(m, n, [r, c + 1], 2, turn + 1); // 우
      mover(m, n, [r + 1, c], 3, turn + 2); // 하
      mover(m, n, [r, c - 1], 4, turn + 3); // 좌
    }
    if (cur === 3) {
      mover(m, n, [r - 1, c], 1, turn + 3); // 상
      mover(m, n, [r, c + 1], 2, turn + 2); // 우
      mover(m, n, [r + 1, c], 3, turn + 1); // 하
      mover(m, n, [r, c - 1], 4, turn + 2); // 좌
    }
    if (cur === 4) {
      mover(m, n, [r - 1, c], 1, turn + 2); // 상
      mover(m, n, [r, c + 1], 2, turn + 3); // 우
      mover(m, n, [r + 1, c], 3, turn + 2); // 하
      mover(m, n, [r, c - 1], 4, turn + 1); // 좌
    }
  }
  mover(room.length, room[0].length, src, sDir, 1);
  const [row, col] = dst;
  // 리턴하기 전 현재의 방향값에 따라 도착시의 방향에 따른 추가 턴수가 필요함
  // 그거는 아직 구현을 생각 못해봤음, 우선은 현재 값을 리턴시켜보기로 함
  return room[row][col] - 1;
};

4. 레퍼런스

const robotPath2 = function (room, src, sDir, dst, dDir) {
  // 가로와 세로의 길이
  const R = room.length;
  const C = room[0].length;
  // 4가지 방향: 위(1), 오른쪽(2), 아래(3), 왼쪽(4)
  // 차례대로 [방향, 상하이동, 좌우이동]
  const MOVES = [
    [1, -1, 0], // UP
    [2, 0, 1], // RIGHT
    [3, 1, 0], // DOWN
    [4, 0, -1], // LEFT
  ];

  // 좌표가 유효한 좌표인지 확인하는 함수
  const isValid = (row, col) => row >= 0 && row < R && col >= 0 && col < C;

  // 각 위치별 최소의 동작으로 도달 가능한 경우의 방향을 저장
  const directions = [];
  // 각 위치별 최소 동작의 수를 저장. 편의상 거리(dist)로 표현
  const dist = [];
  for (let row = 0; row < R; row++) {
    directions.push(Array(C).fill(0));
    dist.push(Array(C).fill(Number.MAX_SAFE_INTEGER));
  }

  // bfs 구현을 위해 큐를 선언한다.
  const queue = Array(R * C);
  let front = 0;
  let rear = 0;
  const isEmpty = (queue) => front === rear;
  const enQueue = (queue, pos) => {
    queue[rear] = pos;
    rear++;
  };
  const deQueue = (queue) => {
    return queue[front++];
  };

  // 출발 지점의 좌표
  const [sRow, sCol] = src;
  directions[sRow][sCol] = sDir;
  dist[sRow][sCol] = 0;

  // 목표 지점의 좌표
  const [dRow, dCol] = dst;

  enQueue(queue, [sRow, sCol]);
  while (isEmpty(queue) === false) {
    const [row, col] = deQueue(queue);
    const dir = directions[row][col];

    for (move of MOVES) {
      const [nDir, rDiff, cDiff] = move;
      // 이동할 좌표
      const nRow = row + rDiff;
      const nCol = col + cDiff;

      // 유효한 좌표가 아니거나
      // 해당 좌표가 장애물(1)인 경우 건너뛴다.
      if (isValid(nRow, nCol) === false || room[nRow][nCol] === 1) continue;

      // 현재 위치의 방향과 목표 위치의 방향과의 차이
      const dDiff = Math.abs(nDir - dir);
      let candidate;
      if (dDiff === 0) {
        // 차이가 없는 경우
        // 출발 지점에서의 방향과 이동하려는 방향이 같은 경우
        // 직진만 하면 되지만 그러기 위해서는 1로 초기화 되어야 한다.
        candidate = dist[row][col] || 1;
      } else if (dDiff === 2) {
        // 2번 회전해야 하는 경우: 회전 2 + 직진 1
        candidate = dist[row][col] + 3;
      } else {
        // 1번만 회전해도 되는 경우: 회전 1 + 직진 1
        candidate = dist[row][col] + 2;
      }

      if (nRow === dRow && nCol === dCol) {
        // 다음에 도달하는 곳이 목표 지점인 경우
        // 목표 방향까지 고려해서 필요한 거리를 계산한다.
        const dDiff = Math.abs(nDir - dDir);
        if (dDiff === 0) {
          candidate = candidate;
        } else if (dDiff === 2) {
          candidate = candidate + 2;
        } else {
          candidate = candidate + 1;
        }
      }

      if (candidate < dist[nRow][nCol]) {
        // 유망한 좌표는 큐에 삽입한다.
        enQueue(queue, [nRow, nCol]);
        dist[nRow][nCol] = candidate;
        // 방향은 전부 같다.
        directions[nRow][nCol] = nDir;
      }
    }
  }

  return dist[dRow][dCol];
};