[Javascript] 프로그래머스 - 미로 탈출

문제 설명

주어진 직사각형 격자 형태의 미로에서 출발 지점(S)에서 시작하여, 레버(L)를 당긴 후 출구(E)까지 도달하는 최소 시간을 구하는 문제입니다. 미로에서 이동할 수 있는 곳은 통로(O)와 출구(E), 레버(L)이며, 벽(X)은 지나갈 수 없습니다. 이동에는 1초가 걸리며, 탈출이 불가능한 경우 -1을 반환해야 합니다.

---

제한 사항

• 미로의 크기는 5 ≤ 행의 개수, 열의 개수 ≤ 100
• 미로는 'S', 'E', 'L', 'O', 'X' 문자로 이루어짐
• 시작 지점(S), 출구(E), 레버(L)은 각각 하나씩 존재
• 출구(E)는 레버를 당기지 않아도 지나갈 수 있음

---

해결 방법

알고리즘: 너비 우선 탐색 (BFS)

1. 위치 및 방문 배열 초기화
   • 미로를 순회하며 시작 지점(S), 출구(E), 레버(L)의 위치를 저장
   • visit 배열을 사용하여 최소 이동 시간을 기록하며, 레버를 당긴 후 상태(lever=1)와 당기지 않은 상태(lever=0)를 구분
2. BFS 탐색
   • 시작 지점(S)에서 BFS 탐색을 수행
   • 네 방향(상, 하, 좌, 우)으로 이동하며 이동 가능한 곳이면 큐에 삽입
   • 레버(L)에 도달하면 상태를 갱신하여 다시 탐색 수행
3. 출구(E) 도달 확인
   • BFS 과정에서 출구(E)에 도달한 경우 최소 시간을 갱신
   • 탐색이 종료될 때까지 도달하지 못하면 -1 반환

---

시간 복잡도

• BFS 탐색이므로 O(N × M) (N: 행의 개수, M: 열의 개수)
• 최악의 경우 100×100=10,000번의 탐색 수행 가능

---

구현 코드

class Queue {
  constructor() {
    this.queue = [];
    this.frontIndex = 0;
  }

  enqueue(value) {
    this.queue.push(value);
  }

  dequeue() {
    if (this.queue.length === this.frontIndex) return null;
    return this.queue[this.frontIndex++];
  }

  isEmpty() {
    return this.queue.length === this.frontIndex;
  }
}

function solution(maps) {
  const rows = maps.length;
  const cols = maps[0].length;
  const visit = Array.from({ length: rows }, () =>
    Array.from({ length: cols }, () => [Infinity, Infinity])
  );
  const q = new Queue();
  const my = [0, 1, 0, -1];
  const mx = [1, 0, -1, 0];
  let answer = -1;
  let ey, ex, ly, lx;

  for (let i = 0; i < rows; ++i) {
    for (let j = 0; j < cols; ++j) {
      if (maps[i][j] === "O" || maps[i][j] === "X") {
        continue;
      } else if (maps[i][j] === "S") {
        q.enqueue({ y: i, x: j, lever: 0, time: 0 });
        visit[i][j][0] = 0;
      } else if (maps[i][j] === "E") {
        ey = i;
        ex = j;
      } else if (maps[i][j] === "L") {
        ly = i;
        lx = j;
      }
    }
  }

  while (!q.isEmpty()) {
    let { x, y, lever, time } = q.dequeue();

    if (y === ly && x === lx && time < visit[y][x][1]) {
      visit[y][x][1] = time;
      lever = 1;
    }

    if (y === ey && x === ex && lever === 1) {
      answer = time;
      break;
    }

    for (let i = 0; i < 4; ++i) {
      const nextY = y + my[i];
      const nextX = x + mx[i];
      const nextTime = time + 1;

      if (
        nextY < 0 ||
        nextX < 0 ||
        nextY >= rows ||
        nextX >= cols ||
        maps[nextY][nextX] === "X" ||
        nextTime >= visit[nextY][nextX][lever]
      ) {
        continue;
      }

      q.enqueue({ x: nextX, y: nextY, lever, time: nextTime });
      visit[nextY][nextX][lever] = nextTime;
    }
  }

  return answer;
}