프로그래머스 - Level 2. 미로 탈출 / JavaScript (js)

문제설명

문제분석 - 수도코드

이 문제는 BFS 알고리즘을 이용하여 최소 시간을 구하는 문제입니다. 시작 지점부터 출구까지의 최소 시간을 구하면 되는데, 이 때 레버를 끌어야 하는 경우를 고려해야 합니다.

우선 문제에서 주어진 문자열 배열 maps를 2차원 배열로 변환하여 저장합니다. 그리고 시작 지점부터 BFS 탐색을 시작합니다. BFS 탐색을 진행하면서, 현재 위치가 레버인 경우는 레버를 당긴 상태와 끄는 상태를 나누어서 큐에 넣어줍니다. 이 때 레버를 당긴 상태에서는 레버 위치에서부터 탐색을 시작하고, 끄는 상태에서는 현재 위치에서부터 탐색을 시작합니다. 이렇게 함으로써 레버를 끄지 않고 출구까지 갈 수 있는 경우와 레버를 끄고 출구까지 갈 수 있는 경우를 모두 고려할 수 있습니다.

마지막으로, BFS 탐색을 진행하면서 도착한 위치가 출구인 경우, 그 위치까지의 시간을 반환하면 됩니다. 모든 BFS 탐색을 진행한 후에도 출구에 도달하지 못한 경우는 -1을 반환합니다.

이해하기 쉽게 코드작성하기

function solution(maps) {
  // 좌표를 찾는 함수
  function findPosition(maps, target) {
    for (let i = 0; i < maps.length; i++) {
      for (let j = 0; j < maps[0].length; j++) {
        if (maps[i][j] === target) {
          return [i, j];
        }
      }
    }
    return [-1, -1];
  }

  // BFS 알고리즘을 이용하여 최단 거리를 구하는 함수
  function bfs(maps, start, end) {
    // 방문 여부를 저장하는 배열
    let visited = Array.from(Array(maps.length), () => Array(maps[0].length).fill(false));
    // 최단 경로를 저장하는 배열
    let path = Array.from(Array(maps.length), () => Array(maps[0].length).fill(null));
    // 시작 지점을 큐에 넣고 방문 표시
    let queue = [[start[0], start[1], null]];
    visited[start[0]][start[1]] = true;
    // 거리를 저장하는 변수
    let distance = 0;
    // 큐가 빌 때까지 반복
    while (queue.length > 0) {
      // 현재 큐의 길이만큼 반복
      let size = queue.length;
      for (let i = 0; i < size; i++) {
        // 큐에서 칸을 꺼냄
        let [x, y, prev] = queue.shift();
        // 만약, 출구에 도달했다면 거리를 반환
        if (x === end[0] && y === end[1]) {
          // 레버까지의 최단 경로를 따라가면서 방문한 칸을 벽으로 바꿈
          while (prev !== null) {
            let [px, py] = prev;
            maps[px][py] = "X";
            prev = path[px][py];
          }
          return distance;
        }
        // 상하좌우로 이동할 수 있는 칸을 확인
        let dx = [-1, 1, 0, 0];
        let dy = [0, 0, -1, 1];
        for (let j = 0; j < 4; j++) {
          // 다음 칸의 좌표
          let nx = x + dx[j];
          let ny = y + dy[j];
          // 다음 칸이 미로 범위 안에 있고, 방문하지 않았고, 벽이 아니라면
          if (nx >= 0 && nx < maps.length && ny >= 0 && ny < maps[0].length && !visited[nx][ny] && maps[nx][ny] !== "X") {
            // 다음 칸을 큐에 넣고 방문 표시
            queue.push([nx, ny, [x, y]]);
            visited[nx][ny] = true;
            // 다음 칸의 최단 경로를 저장
            path[nx][ny] = [x, y];
          }
        }
      }
      // 거리를 1 증가
      distance++;
    }
    // 출구에 도달할 수 없다면 -1을 반환
    return -1;
  }

  // 시작 지점, 레버, 출구의 좌표를 찾음
  let start = findPosition(maps, "S");
  let lever = findPosition(maps, "L");
  let exit = findPosition(maps, "E");

  // 시작 지점에서 레버까지의 최단 거리를 구함
  let startToLever = bfs(maps, start, lever);
  // 레버에서 출구까지의 최단 거리를 구함
  let leverToExit = bfs(maps, lever, exit);

  // 두 최단 거리를 더하여 최소 시간을 구함
  let minTime = startToLever + leverToExit;
  // 만약, 레버나 출구에 도달할 수 없다면 -1을 반환
  if (startToLever === -1 || leverToExit === -1) {
    return -1;
  }
  // 그렇지 않으면 최소 시간을 반환
  return minTime;
}