[백준2178_자바스크립트(javascript)] - 미로 탐색

🔴 문제

미로 탐색

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [nm, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');

const [n, m] = nm.split(' ').map((it) => Number(it));
const maps = inputs.map((it) => it.split('').map((it) => Number(it)));

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

function bfs(x, y) {
  const q = [];
  q.push([x, y]);

  while (q.length) {
    const [x, y] = q.shift();

    for (let i = 0; i < 4; i++) {
      // 이동할 좌표 값 명시
      const nx = x + dx[i];
      const ny = y + dy[i];

      // 좌표 값이 범위를 벗어난다면
      if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
      // 못지나간다면 continue
      if (maps[nx][ny] === 0) continue;
      // 지나갈 수 있다면
      if (maps[nx][ny] === 1) {
        // 해당 위치에 방문 횟수 증가
        maps[nx][ny] = maps[x][y] + 1;
        // 좌표 값 큐에 추가
        q.push([nx, ny]);
      }
    }
  }
  return maps[n - 1][m - 1];
}

console.log(bfs(0, 0));

🟢 풀이

최단 거리를 구하는 문제니까 bfs로 풀면 된다.(보통 최단거리는 bfs로 풀이한다.)
기본 문제 유형이라 공식에 적용시켜주면된다.
큐를 만들어주고 큐가 빌때까지 반복을 돌려주면서 4개의 방향을 다 탐색한다.
탐색하면서 범위에 벗어나거나, 못지나가는 구역일 경우 탐색을 중단한다.
지나갈 수 있다면 해당 위치에 방문 횟수를 증가해준 후 다음에 탐색할 좌표값을 큐에 넣어준다.

🔵 Ref