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

문제

미로 탈출

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

 

 

예시 코드

class Queue {
  constructor() {
    this.inbox = [];
    this.outbox = [];
  }

  enqueue(data) {
    this.inbox.push(data);
  }

  dequeue() {
    if (!this.outbox.length) {
      while (this.inbox.length) {
        this.outbox.push(this.inbox.pop());
      }
    }

    return this.outbox.pop();
  }

  size() {
    return this.inbox.length + this.outbox.length;
  }

  isEmpty() {
    return this.size() === 0;
  }
}

function solution(maps) {
  const n = maps.length;
  const m = maps[0].length;
  const S = [];
  const E = [];
  const L = [];

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (maps[i][j] === "S") S.push(i, j);
      if (maps[i][j] === "E") E.push(i, j);
      if (maps[i][j] === "L") L.push(i, j);
    }
  }

  let sToL = bfs(S, L);
  if (sToL === -1) return -1;
  let lToE = bfs(L, E);
  if (lToE === -1) return -1;

  return sToL + lToE;

  function bfs(S, E) {
    const dx = [0, -1, 0, 1];
    const dy = [1, 0, -1, 0];
    const visited = Array.from({ length: n }, () => Array(m).fill(false));
    const queue = new Queue();
    visited[S[0]][S[1]] = true;
    queue.enqueue([S[0], S[1], 0]);

    while (!queue.isEmpty()) {
      const [cx, cy, dist] = queue.dequeue();
      if (cx === E[0] && cy === E[1]) return dist;

      for (let i = 0; i < 4; i++) {
        const nx = cx + dx[i];
        const ny = cy + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (maps[nx][ny] === "X") continue;
        if (visited[nx][ny]) continue;
        visited[nx][ny] = true;
        queue.enqueue([nx, ny, dist + 1]);
      }
    }

    return -1;
  }
}

 

풀이

시작 지점에서 레버를 걸쳐 출구까지 가는데 걸리는 최소 시간을 구하는 문제입니다.

시작 지점에서 레버까지의 최소 시간 + 레버에서 출구까지의 최소 시간을 구하면 됩니다.

둘 중 하나라도 도달할 수 없다면 -1을 반환합니다.

 

BFS를 사용하여 해결할 수 있습니다.