문제 링크

https://programmers.co.kr/learn/courses/30/lessons/60063

나의 코드

function solution(board) {
  var answer = 0;
  const len = board.length;
  const dy = [-1, 0, 1, 0],
    dx = [0, 1, 0, -1];
  const visit = {};
  const q = [{ y1: 0, x1: 0, y2: 0, x2: 1 }];
  visit[JSON.stringify(q[0])] = 0;

  while (q.length) {
    const curState = { ...q[0] };
    const { y1, x1, y2, x2, dir } = q.shift();
    if (
      (y1 === len - 1 && x1 === len - 1) ||
      (y2 === len - 1 && x2 === len - 1)
    )
      return visit[JSON.stringify(curState)];
    for (let i = 0; i < 4; ++i) {
      const ny1 = y1 + dy[i],
        nx1 = x1 + dx[i],
        ny2 = y2 + dy[i],
        nx2 = x2 + dx[i];
      const nextState = { y1: ny1, x1: nx1, y2: ny2, x2: nx2, dir };
      if (isRangeOut(ny1, nx1)) continue;
      if (isRangeOut(ny2, nx2)) continue;
      if (board[ny1][nx1] === 1 || board[ny2][nx2] === 1) continue;
      checkAndPush(visit, nextState, curState);
      const rotate1 = { y1, x1, y2: ny1, x2: nx1 };
      checkAndPush(visit, rotate1, curState);
      const rotate2 = { y1: ny2, x1: nx2, y2, x2 };
      checkAndPush(visit, rotate2, curState);
    }
  }

  function checkAndPush(visit, nextState, curState) {
    if (visit[JSON.stringify(nextState, curState)] !== undefined) return;
    q.push({ ...nextState });
    visit[JSON.stringify(nextState)] = visit[JSON.stringify(curState)] + 1;
  }

  function isRangeOut(y1, x1) {
    if (y1 < 0 || y1 >= len || x1 < 0 || x1 >= len) return true;
    return false;
  }

  return answer;
}

풀이

1. 초기 좌표값을 배열에 넣고 BFS를 실행한다.
2. 반복문은 상하좌우를 체크하기위해 4번을 실행한다.
3. 단순히 이동했을 때와 시계 방향으로 회전했을 때, 반시계 방향으로 회전했을 때를 체크하여 배열에 넣어준다.

로봇이 회전을 하기 위해서는 ny1 nx1 ny2 nx2 가 결국 다 0이어야 한다. 또한 회전은 현재 이동하려는 방향에 대해 시계 방향, 반시계 방향 이렇게 2가지 경우만을 생각하면 되는데 결국 다음 상태의 좌표 값은 각각 축이 되는 칸으로부터 대각선 방향에 있는 칸이다.

const rotate1 = { y1, x1, y2: ny1, x2: nx1 };
const rotate2 = { y1: ny2, x1: nx2, y2, x2 };

따라서 rotate1 rotate2 로 각각 회전하는 경우의 상태값을 처리할 수 있다.

반성할 점

처음 문제를 풀면서 회전때문에 visit을 체크할 때 로봇의 상태(로봇이 세로로 있는지 가로로 있는지)도 고려해야 하는 줄로 알고 착각하여 다소 시간이 오래걸렸다. 근데 고려해야할 점이 많아져 잠시 고민을 했었다. 코딩을 멈추고 다시 생각해보니 로봇의 상태는 신경쓰지 않고 그대로 시계 방향 회전과 반시계 방향 회전이 가능한지만 체크하면 된다고 판단하였다. 풀고 나면 이렇게 간단한 문제를 깊게 생각하지 않고 섣부르게 코딩하여 오랜 시간이 걸렸던 것 같다.