[Programmers] 미로탈출 - Javascript

INDEX

https://school.programmers.co.kr/learn/courses/30/lessons/159993?language=javascript 

프로그래머스

 

Solution

그래프 문제는 DFS 혹은 BFS로 대부분 풀 수 있습니다.

이 문제는 BFS로 풀었습니다.

위 문제를 정말 쉽게 해석하면 벽('X') 인 곳을 피해 레버('L')가 있는 곳에 도착하고 다시 도착지('E')까지 도착하는 가장 짧은 경로를 구하는 문제입니다.

즉, 출발지부터 레버가 있는 곳 까지의 경로를 구하고 레버에서부터 도착지까지의 경로를 더하면 됩니다.

 

우선 출발지와 레버, 도착지의 좌표를 구합니다.

let start, lever, exit;
for (let i = 0; i < maps.length; i++) {
    for (let j = 0; j < maps[0].length; j++) {
      if (maps[i][j] === "S") start = [i, j];
      else if (maps[i][j] === "L") lever = [i, j];
      else if (maps[i][j] === "E") exit = [i, j];
    }
}

 

그리고 경로를 구하는 함수 bfs 가 있다고 할 때 총경로를 구하는 코드는 아래와 같습니다.

const distance1 = bfs(start, lever);
if (distance1 === 0) return -1;
const distance2 = bfs(lever, exit);
if (distance2 === 0) return -1;
console.log(distance1, distance2);
return distance1 + distance2;

더 이상 갈 곳이 없다면 -1을 return 해야 하고 불필요한 탐색(distance1 이 0인데 distance2를 탐색하는)을 막기 위해 합을 구하기 전에 검사를 먼저 합니다.

 

이제 가장 짧은 경로를 구하는 함수 bfs는 아래와 같습니다. 코드를 보기에 앞서 최단 경로를 어떻게 구할 것인가부터 설명하겠습니다.

한 번 이동할 때마다 칸의 값을 걸음수로 변환합니다. 이미 갔던 곳 (0이 아닌 칸) 은 가지 않습니다.

function bfs(start, end) {
    let visitedMap = [];
    for(let i=0; i<maps.length;i++){
      let arr = new Array(maps[0].length).fill(0);
      visitedMap.push(arr);
    } //0으로 채워진 2차원 배열을 만듭니다.

    let q = [start];
    while (q.length !== 0) {
      const [row, col] = q.shift();
      for (let j = 0; j < 4; j++) {
        const nRow = row + moveRow[j];
        const nCol = col + moveCol[j];
        if (
          maps[nRow] &&
          maps[nRow][nCol] &&
          !visitedMap[nRow][nCol] &&
          maps[nRow][nCol] !== "X"
        ) {
          visitedMap[nRow][nCol] = visitedMap[row][col] + 1; 
          q.push([nRow, nCol]);
        }
      }
    }
    return visitedMap[end[0]][end[1]]; //도착지점의 걸음 수를 반환합니다.
  }

 

*주의 점

Javascript 에서 2차원 배열, 특히 특정한 값으로 채워진 2차원 배열을 만들 때 주의할 점이 있습니다.

[
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]


let visitedMap = new Array(5).fill(new Array(5).fill(0));

위처럼 짜면 visitedMap의 원소 배열이 모두 같은 주소값을 갖게 되어 한 원소만 변경해도 모든 원소가 변경됩니다.

let visitedMap = new Array(5).fill(new Array(5).fill(0));
visitedMap[0][0] = 1;
[
    [1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0]
]

따라서 조금 길더라도 아래와 같은 방법으로 2차원 배열을 만드는 게 좋습니다.

let visitedMap = [];
for(let i=0; i<maps.length;i++){
  let arr = new Array(maps[0].length).fill(0);
  visitedMap.push(arr);
}

 

전체코드

function solution(maps) {
  const moveRow = [1, -1, 0, 0];
  const moveCol = [0, 0, 1, -1];

  function bfs(start, end) {
    let visitedMap = [];
    for(let i=0; i<maps.length;i++){
      let arr = new Array(maps[0].length).fill(0);
      visitedMap.push(arr);
    }

    let q = [start];
    while (q.length !== 0) {
      const [row, col] = q.shift();
      for (let j = 0; j < 4; j++) {
        const nRow = row + moveRow[j];
        const nCol = col + moveCol[j];
        if (
          maps[nRow] &&
          maps[nRow][nCol] &&
          !visitedMap[nRow][nCol] &&
          maps[nRow][nCol] !== "X"
        ) {
          visitedMap[nRow][nCol] = visitedMap[row][col] + 1;
          q.push([nRow, nCol]);
        }
      }
    }
    return visitedMap[end[0]][end[1]];
  }
  let start, lever, exit;
  for (let i = 0; i < maps.length; i++) {
    for (let j = 0; j < maps[0].length; j++) {
      if (maps[i][j] === "S") start = [i, j];
      else if (maps[i][j] === "L") lever = [i, j];
      else if (maps[i][j] === "E") exit = [i, j];
    }
  }
  const distance1 = bfs(start, lever);
  if (distance1 === 0) return -1;
  const distance2 = bfs(lever, exit);
  if (distance2 === 0) return -1;
  return distance1 + distance2;
}