프로그래머스 JS 미로 탈출 (BFS 최단거리 찾기)

미로 탈출 (120) 문제 보기

문제 조건 

// 1x1 칸, 격자 미로

// 통로 "O" 또는 벽 "X"

// 탈출구 "E" 는 레버 "L" 로 열 수 있음

// 최대한 빨리 나가기

// S : 시작 지점

// E : 출구

// L : 레버

// O : 통로

// X : 벽

// 탈출 못하면 -1

// 레버 찾아 열기

// > 탈출구 찾아 열기

 

---

문제 풀이

// 지도 내 target 좌표를 반환
function getTargetPos(maps, n, m, target) {
    for (let i = 0; i < maps.length; i++) {
      for (let j = 0; j < maps[0].length; j++) {
        if (isInGrid(i, j, n, m) && maps[i][j] === target) {
          return [i, j];
        }
      }
    }
  }
  
  // 지도 내에 위치한 영역인지 확인
  function isInGrid(x, y, n, m) {
    return x >= 0 && x < n && y >= 0 && y < m;
  }
  
  // 지도 탐색, 최단거리 반환
  function BFS(queue, maps, target) {
    const [n, m] = [maps.length, maps[0].length]; // 지도 크기 n*m
    const dir = [
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1],
    ];
  
    while (queue.length) {
      let [x, y, curMove] = queue.shift();
  
      for (let i = 0; i < dir.length; i++) {
        const dx = x + dir[i][0];
        const dy = y + dir[i][1];
        if (isInGrid(dx, dy, n, m) && maps[dx][dy] !== "X") {
          if (maps[dx][dy] === target) {
            return curMove + 1;
          }
          maps[dx][dy] = "X";
          queue.push([dx, dy, curMove + 1]);
        }
      }
    }
  
    return -1;
  }
  
  function solution(maps) {
    const [n, m] = [maps.length, maps[0].length]; // 지도 크기 n*m
    const leverMaps = maps.map((item) => item.split("")); // 레버 탐색 지도
    const exitMaps = maps.map((item) => item.split("")); // 출구 탐색 지도
    const startPos = [...getTargetPos(maps, n, m, "S")]; // "S" 위치
    const leverPos = [...getTargetPos(maps, n, m, "L")]; // "L" 위치
  
    let leverMove = BFS([[...startPos, 0]], leverMaps, "L"); // "S"에서 "L"까지 최단거리
    if (leverMove === -1) return -1;
  
    let exitMove = BFS([[...leverPos, 0]], exitMaps, "E"); // "L"에서 "E"까지 최단거리
    if (exitMove === -1) return -1;
  
    return leverMove + exitMove;
  }
  
solution(["SLEOO", "OOOOO", "OOOOO", "OOOOO", "OOOOO"]);

미로 탈출을 위해 최단거리를 구하는 문제입니다.

 

BFS를 활용하여 최단거리를 구하면 됩니다.

 

1. 우선 시작 "S" 좌표에서 레버"L" 좌표로 이동합니다.

2. "L"좌표로 접근할 수 없다면 -1을 반환합니다.

3. "L"좌표에서 "E" 좌표로 이동합니다. 
4. "E"좌표로 접근할 수 없다면 -1을 반환합니다.

5. "E"좌표로 접근했다면 "S" -> "L" 이동거리와 "L" -> "E" 이동거리의 합을 반환합니다.