[JS] 미로 탈출 명령어

처음에는 일반 미로 문제 풀듯이 dfs를 사용해서 풀어보았다.

 

결국 사전순이란게 미로의 길을 먼저찾는 우선순위를 정해줬다고 생각했다.

 

function solution(n, m, x, y, r, c, k) {
  const map = [...Array(n + 1)].map((_) => Array(m + 1).fill("."));
  map[r][c] = "E";

  const dy = [-1, 0, 0, 1];
  const dx = [0, 1, -1, 0];
  const dOrder = "urld";

  const stk = [[x, y, ""]];

  while (stk.length) {
    const [cy, cx, order] = stk.pop();
    if (order.length === k) {
      if (map[cy][cx] === "E") return order;
      else continue;
    }

    for (let d = 0; d < 4; d++) {
      const ny = cy + dy[d];
      const nx = cx + dx[d];
      const nOrder = order + dOrder[d];
      if (0 < ny && ny <= n && 0 < nx && nx <= m) {
        stk.push([ny, nx, nOrder]);
      }
    }
  }
  return "impossible";
}

 

 

문제를 처음 봤을때부터 k가 최대 2500이길래 dfs나 bfs로 못 풀수도 있겠다.. 라는 생각을 하긴 했는데 역시 테스트를 통과하지 못했다.

 

 

이리저리 생각하다가 결국 목적지에 도착했을때 이동해야하는 거리가 홀수라면 impossible이 나온다는 점을 발견했고, 뭔가 그리디 알고리즘을 활용해서 풀어볼만한 문제라고 생각을 했다.

 

시작점이나 끝점을 옮기면서 이리저리 옮겨볼까 등등 여러 생각을 하다가 다른 분의 아이디어를 보게 되었는데 참 괜찮은 방법이었다.

 

우선 끝점까지 이동을 한 이후, (n,1)을 찍고오는것으로 계산을 하는 것이다.

 

s -> e -> (n,1) -> e

 

1. (n,1)을 찍고올 만한 충분한 거리(k)가 안되는 경우 => n,1로 가다가 돌아오면 된다.

2. (n,1)을 찍고와도 거리가 남는경우(k) => 해당 자리에서 rl을 남은 횟수만큼 반복하면 된다.

 

 

이렇게 할 수 있는 이유는 지도에 장애물이 없기 때문에  d , l , r ,u움직여야 하는 총 횟수만 구하고 해당 우선순위대로 나열만 한다면 order을 만들어낼 수 있기 때문이다.

 

즉 해당 문제의 접근 방식은 아래와 같다.

 

1. impossible인지 아닌지 판단 (맨해튼 거리 방식을 활용해서 계산하면 쉽게 구할 수 있다.)

2. s -> e -> (n,1) -> e 순서로 이동하게 함

3. k가 부족하거나 남는경우 이를 고려하여 d,l,r,u 이동의 총량을 구한다.

 

 

구한 총량을 d -> l -> r -> u 순서대로 붙여서 사전순으로 만든다.

 

 

function solution(n, m, x, y, r, c, k) {
  let ret = "";
  let dist = Math.abs(x - r) + Math.abs(y - c);
  k -= dist;
  if (k < 0 || k % 2 != 0) return "impossible";

  const direction = { d: 0, l: 0, r: 0, u: 0 };
  if (x > r) direction.u += x - r;
  else direction.d += r - x;
  if (y > c) direction.l += y - c;
  else direction.r += c - y;

  ret += "d".repeat(direction.d);
  const d = Math.min(k / 2, n - (x + direction.d));
  ret += "d".repeat(d);
  direction.u += d;
  k -= 2 * d;

  ret += "l".repeat(direction.l);
  const l = Math.min(k / 2, y - direction.l - 1);
  ret += "l".repeat(l);
  direction.r += l;
  k -= 2 * l;

  ret += "rl".repeat(k / 2);
  ret += "r".repeat(direction.r);
  ret += "u".repeat(direction.u);
  return ret;
}