[프로그래머스 lev3/JS] 미로 탈출 명령어

문제 출처

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

나의 풀이

1차 시도 (1개 시간초과 실패, 97.4/100)

문제에서 사전순을 요구했으므로 처음부터 설정을 사전 순서대로 맞춰준다.
(d, l, r, u 순이므로 이 순서대로 direction 배열과 객체를 만들어준다.)

• 이때 위/아래 이동 방향이 거꾸로임을 주의해야 한다(배열이므로)
• grid를 만들 때 생각하기 쉽게 애초에 index 0을 제외한다.

제출할 answer의 값을 최대값으로 잡고자 "z" * k 로 나열한다.

그리고 dfs를 진행해주는데, 예외처리를 여러 개 해줘야 한다.

• 위치 범위를 넘어서는 애들이 불필요하게 재귀를 돌지 않게 해준다(dy <= n && dy > 0 && dx <= m && dx > 0).
• 거리가 k 보다 크면 종료해준다.
• 현재 진행된 거리가 목표지점보다 멀어지면 이 또한 종료해준다. (Math.abs(dy - r) + Math.abs(dx - c) + L + 1)

그리고 애초에 순서대로 direction을 설정했기 때문에
한번이라도 답을 찾으면 그게 최대값이다. 그래서 답을 찾자마자 종료해준다.

재귀를 전부 돌았는데도 "z" * k이면 불가능하다고 판단해준다.

마지막 1개가 시간초과가 발생한다. 아무래도 불가능한 답일 때 재귀를 끝까지 돌아야 해서 시간초과가 발생하는 것 같다.

function solution(n, m, x, y, r, c, k) {
  let grid = Array.from({ length: n + 1 }, () => new Array(m + 1).fill("."));

  grid[x][y] = "S";
  grid[r][c] = "E";

  let d = [
    [1, 0], // d
    [0, -1], // l
    [0, 1], // r
    [-1, 0], // u
  ];

  // up/down 순서 거꾸로 주의
  // 최대한 d, l, r, u 순서대로 먼저 도는 게 빠르니까.
  let str = {
    0: "d",
    1: "l",
    2: "r",
    3: "u",
  };

  // let set = new Set();
  let answer = "z".repeat(k);

  function dfs(L, py, px, sum, dist) {
    if (L > k) return;
    if (dist > k) return; // 현재 거리가 목표지점에서 멀어지면 멈춘다.
    if (L === k && py === r && px === c) {
      // set.add(sum);
      if (answer > sum) {
        answer = sum;
        return;
      }
    }
    if (answer !== "z".repeat(k)) return;

    for (let i = 0; i < 4; i++) {
      dy = py + d[i][0];
      dx = px + d[i][1];

      // 편의상 index 0을 제거했으므로 dy, dx도 0보다 크거나 같은 게 아니라 무조건 커야 한다.
      if (dy <= n && dy > 0 && dx <= m && dx > 0) {
        // console.log(dy, dx, sum + str[i]);

        dfs(
          L + 1,
          dy,
          dx,
          sum + str[i],
          Math.abs(dy - r) + Math.abs(dx - c) + L + 1
        );
      }
    }
  }
  dfs(0, x, y, "", k);

  // if (set.size === 0) return "impossible";
  if (answer === "z".repeat(k)) return "impossible";

  return answer;

  // let arrFromSet = Array.from(set);
  // arrFromSet.sort();
  // return arrFromSet[0];
}

console.log(solution(3, 4, 2, 3, 3, 1, 5)); // "dllrl"
// console.log(solution(2, 2, 1, 1, 2, 2, 2)); // "dr"
// console.log(solution(3, 3, 1, 2, 3, 3, 4)); // "impossible"

2차 시도 (통과)

let fastAnswer = k - (Math.abs(x - r) + Math.abs(y - c));
if (fastAnswer < 0 || fastAnswer % 2 != 0) return "impossible";

역시 impossible일 때 재귀를 끝까지 도는 게 문제였다.
처음 조건 자체가 불가능한 거리로 주어질 경우 시작하자마자 종료 조건을 설정해주니까 tc31을 바로 풀었다.

function solution(n, m, x, y, r, c, k) {
  let grid = Array.from({ length: n + 1 }, () => new Array(m + 1).fill("."));

  grid[x][y] = "S";
  grid[r][c] = "E";

  let fastAnswer = k - (Math.abs(x - r) + Math.abs(y - c));
  if (fastAnswer < 0 || fastAnswer % 2 != 0) return "impossible";

  let d = [
    [1, 0], // d
    [0, -1], // l
    [0, 1], // r
    [-1, 0], // u
  ];

  // up/down 순서 거꾸로 주의
  // 최대한 d, l, r, u 순서대로 먼저 도는 게 빠르니까.
  let str = {
    0: "d",
    1: "l",
    2: "r",
    3: "u",
  };

  // let set = new Set();
  let answer = "z".repeat(k);

  function dfs(L, py, px, sum, dist) {
    if (L > k) return;
    if (dist > k) return; // 현재 거리가 목표지점에서 멀어지면 멈춘다.
    if (L === k && py === r && px === c) {
      // set.add(sum);
      if (answer > sum) {
        answer = sum;
        return;
      }
    }
    if (answer !== "z".repeat(k)) return;

    for (let i = 0; i < 4; i++) {
      dy = py + d[i][0];
      dx = px + d[i][1];

      // 편의상 index 0을 제거했으므로 dy, dx도 0보다 크거나 같은 게 아니라 무조건 커야 한다.
      if (dy <= n && dy > 0 && dx <= m && dx > 0) {
        // console.log(dy, dx, sum + str[i]);

        dfs(
          L + 1,
          dy,
          dx,
          sum + str[i],
          Math.abs(dy - r) + Math.abs(dx - c) + L + 1
        );
      }
    }
  }
  dfs(0, x, y, "", k);

  // if (set.size === 0) return "impossible";
  if (answer === "z".repeat(k)) return "impossible";

  return answer;

  // let arrFromSet = Array.from(set);
  // arrFromSet.sort();
  // return arrFromSet[0];
}

다른 풀이

풀이 1

d, l, r, u 순서대로 진행하되 k 길이만큼 전부 찾는 게 아니라 가능한 부분만 먼저 찾는다. 그리고 나서 남은 부분에 대해서는 임의로 가장 빠른 방법을 선택해 채워준다.

문제에서 제시한 조건을 곧이 곧대로 이행하려 하면 효율성을 잡기 어렵다. 주어진 조건의 크기 자체를 줄일 수 있으면 시간을 엄청나게 줄일 수 있다. 완전탐색인 척 하는 함정들을 조심하자.

const mDist = (x, y, r, c) => {
  return Math.abs(x - r) + Math.abs(y - c);
};

const move = (n, m, x, y, r, c) => {
  let dx = [1, 0, 0, -1];
  let dy = [0, -1, 1, 0];

  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i];
    let ny = y + dy[i];

    if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
      return i;
    }
  }
};

function solution(n, m, x, y, r, c, k) {
  let minDist = mDist(x, y, r, c);
  let res = k - minDist;
  let alp = ["d", "l", "r", "u"];

  if (minDist % 2 !== k % 2 || res < 0) return "impossible";

  let answer = "";

  while (minDist < k) {
    let temp = move(n, m, x, y, r, c);
    answer += alp[temp];
    if (temp === 0) x++;
    else if (temp === 1) y--;
    else if (temp === 2) y++;
    else x--;

    minDist = mDist(x, y, r, c);
    k--;
  }

  if (x < r) answer += "d".repeat(r - x);
  if (y > c) answer += "l".repeat(y - c);
  if (y < c) answer += "r".repeat(c - y);
  if (x > r) answer += "u".repeat(x - r);

  return answer;
}

풀이 2

function solution(n, m, x, y, r, c, k) {
  let move = [r - x, y - c, c - y, x - r].map((v) => Math.max(0, v));
  let [dCount, lCount, rCount, uCount] = move;
  let moveSum = move.reduce((a, b) => a + b);

  const diff = k - moveSum;
  if (diff < 0 || diff % 2 == 1) return "impossible";
  const vMove = Math.min(diff / 2, n - x - dCount);
  dCount += vMove;
  uCount += vMove;
  const hMove = diff / 2 - vMove;
  lCount += hMove;
  rCount += hMove;

  let answer = dCount ? "d".repeat(dCount) : "";
  let hStart = y;
  while (lCount > 0) {
    if (hStart > 1) {
      hStart--;
      answer += "l";
    } else {
      answer += "rl";
      rCount--;
    }
    lCount--;
  }
  answer += rCount ? "r".repeat(rCount) : "";
  answer += uCount ? "u".repeat(uCount) : "";
  return answer;
}