백준 2178 미로탐색

문제

제한사항

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

let [n, m] = input.shift().split(' ').map(Number);
let arr = input.map((e) => e.split('').map(Number));
const solution = (n, m, arr) => {
  let dx = [1, 0, -1, 0];
  let dy = [0, 1, 0, -1];
  let map = [...arr];
  const dis = Array.from(Array(n), () => Array(m).fill(0));
  const bfs = (i, j) => {
    let queue = [];
    queue.push([i, j]);
    while (queue.length) {
      let [x, y] = queue.shift();
      for (let i = 0; i < dx.length; i++) {
        let nx = x + dx[i];
        let ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny]) {
          map[nx][ny] = 0;
          dis[nx][ny] = dis[x][y] + 1;
          queue.push([nx, ny]);
        }
      }
    }
  };

  map[0][0] = 0;
  dis[0][0] = 1;
  bfs(0, 0);
  return dis[n - 1][m - 1];
};
console.log(solution(n, m, arr));

• 인프런 미로탐색과는 조금 다르다.
• 그 문제는 가능한 경로의 개수이고, 이문제는 최단거리이다.
• 최단거리이기 때문에 bfs로 푸는 것이 좋다.
• dis배열은 값을 누적해나가기 때문에 잘 활용하면 문제를 푸는데 꽤 도움이 된다.