[JS] 미로 탈출 명령어

문제

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

 

풀이

이 문제의 경우 2차원 배열을 이용해 한정된 횟수 안에 특정 지점까지의 도착 여부를 측정하는 문제이다.

 

이번 문제는 비슷한 유형의 문제들에서 추가된 조건들이 존재한다.

1. 한정된 이동 회수
2. 최단 이동
3. 문자 기준 사전순 빠른 탈출 명령어

1 번의 경우는 문제에서 주어지는 k 값을 이용해 탐색 회수를 한정할 수 있다.

2 번과 3 번의 경우는 문자 기준으로 이동 방향의 정렬(down, left, right, up 순서)을 이용해 탐색 방향의 우선순위를 지정하고, 각 이동시 목표지점과의 멘허탄거리를 측정해 k값 보다 멀어진다면 탐색을 중단한다. 멘하탄 거리를 이용하는 부분을 처음에는 생각하지 못했지만, 해당 조건을 두지 않으면 모든 경우의 수를 탐색하기 때문에 시간초과가 발생한다....

코드

function solution(n, m, x, y, r, c, k) {
  let answer = "z".repeat(k);
  const dir = [
    [1, 0],
    [0, -1],
    [0, 1],
    [-1, 0],
  ];
  const st = ["d", "l", "r", "u"];
  let map = Array.from({ length: n + 1 }, () =>
    Array.from({ length: m + 1 }, () => "x")
  );
  const minMove = Math.abs(r - x) + Math.abs(c - y);

  if (minMove > k || (k - minMove) % 2 !== 0) return "impossible";
  map[x][y] = "S";
  map[r][c] = "E";

  const dfs = (my, mx, tempString, distance) => {
    if (tempString.length > k) return;
    if (distance > k) return;
    if (tempString.length === k) {
      if (map[my][mx] === "E" && answer > tempString) {
        answer = tempString;
        return;
      }
    }
    if (answer !== "z".repeat(k)) return;
    for (let i = 0; i < 4; i++) {
      const ny = my + dir[i][0];
      const nx = mx + dir[i][1];
      if (ny > 0 && ny <= n && nx > 0 && nx <= m) {
        const temp = tempString + st[i];
        dfs(
          ny,
          nx,
          temp,
          Math.abs(ny - r) + Math.abs(nx - c) + tempString.length + 1
        );
      }
    }
  };
  dfs(x, y, "", k);
  return answer !== "z".repeat(k) ? answer : "impossible";
}