[프로그래머스] Lv3. 미로 탈출 명령어- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 3

출처 : 프로그래머스 - 미로 탈출 명령어

문제

제한사항

📌 내가 생각한 풀이

장애물이 존재하지 않고, 주어진 조건의 거리로만 판단하여 재귀문을 종료하기 때문에, 종료조건을 잘 따져야한다.
1. 이동한 거리가 K보다 클경우 -> 조건에 만족하지 않으므로 종료
2. 현재 이동한 거리와 남은 이동거리의 합이 k보다 클경우 -> 도착지점까지 갈 경우 반드시 k크기 때문에 미리 종료한다.
3. 시작점부터 종료지점까지의 거리가 K보다 클 경우 -> 조건에 만족하지 않으므로 종료
4. 시작점부터 종료지점까지의 거리가 K보다 큰데 홀 수 일 경우 -> 조건에 만족하지 않으므로 종료

const dir = {
  0: "d",
  1: "l",
  2: "r",
  3: "u",
};
function solution(n, m, x, y, r, c, k) {
  var answer = "";
  let result = [];
  let dx = [1, 0, 0, -1];
  let dy = [0, -1, 1, 0];
  let board = Array.from(Array(n), () => Array(m).fill("."));
  board[x - 1][y - 1] = "S";
  board[r - 1][c - 1] = "E";
  let fastAnswer = k - (Math.abs(x - r) + Math.abs(y - c));
  if (fastAnswer < 0 || fastAnswer % 2 != 0) return "impossible";
  let queue = [x - 1, y - 1];
  const re = (current, stack) => {
    if (result.length > 0) return;
    if (stack.length > k) return;
    let [nx, ny] = current;
    if (Math.abs(nx - (r - 1)) + Math.abs(ny - (c - 1)) + stack.length > k) {
      return;
    }
    if (stack.length === k && nx === r - 1 && ny === c - 1) {
      result.push(stack);
      return;
    }
    for (var i = 0; i < 4; i++) {
      let lx = nx + dx[i];
      let ly = ny + dy[i];
      if (lx >= 0 && lx < n && ly >= 0 && ly < m) {
        re([lx, ly], stack + dir[i]);
      }
    }
  };
  let a = re(queue, "");
  // console.log(result)

  return result[0];
}

📌 느낀점

시간초과와의 싸움문제였다. 반드시 종료조건을 잘 파악한 다음, 미리 불가능한 경우에 재귀적으로 탐색하지 않고 종료하여 시간초과를 방지하자.