[백준] 2178번 미로 -JavaScript(NodeJS)

문제

2178번: 미로 탐색

 

풀이

사실 문제를 처음 보고서는, BFS 구현에 익숙하지 않아서
모든 방법을 조회해보고 최솟값을 뽑아내도 괜찮겠다는 생각으로 우선 DFS로 접근했다.

 

하지만 결국 시간초과 이슈로, BFS로 해결했다.

 

이 문제는 최단경로 문제에 해당하는데,

BFS는 너비 우선 탐색으로, 특정 지점에 가장 빨리 도착한 경우를 구하기에 적절하다.

 

BFS는 while문과 queue 자료구조를 사용하여 구현할 수 있다.
자바스크립트에서 queue 자료구조의 구현은 배열과 push, shift 메서드를 사용하면 된다.

 

 

미로를 탐색할 때, 현재 위치를 기준으로 동서남북 이동 가능성을 조회하고, 이동하면 되는데
이미 지나온 곳을 다시 방문하지 않기 위해 체크배열을 조회하며 이동하면 최단경로로 도착할 수 있다.

 

예를 들면, 다음과 같은 모습이다.

 

코드

const sol = (input) => {
  const [N, M] = input[0].split(" ").map((v) => +v);
  const adjM = [];
  for (let i = 1; i <= N; i++) adjM.push(input[i].split("").map((v) => +v)); // 미로 행렬
  const check = Array.from({ length: N }, () => Array(M).fill(0)); // 방문 여부를 위한 체크 행렬

  function bfs(row, col) {
    const dx = [-1, 0, 1, 0];
    const dy = [0, 1, 0, -1]; // 현재 위치로부터 동서남북 조회를 위한 dx, dy 배열
    const queue = [];
    queue.push([row, col]);
    check[row][col] = 1;
    while (queue.length) {
      const [x, y] = queue.shift(); // 큐는 FIFO이므로, 맨 앞부터 꺼낸다.
      for (let i = 0; i < 4; i++) {
        const [nx, ny] = [x + dx[i], y + dy[i]]; // (nx, ny)는 이동 가능성이 있는 좌표.
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue; // 미로를 벗어나는 좌표는 제외
        if (adjM[nx][ny] && !check[nx][ny]) { // 길이 있고, 방문하지 않았다면 방문
          check[nx][ny] = check[x][y] + 1; // (x,y)의 값이 (x,y)까지 최단경로에 해당한다.
          queue.push([nx, ny]); // BFS(너비 우선)로 현재 위치에서 갈 수 있는 좌표를 모두 큐에 넣어준다.
        }
      }
    }
  }
  bfs(0, 0);
  return check[N - 1][M - 1];
};

// 백준에서 입력을 받기 위한 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });

 

만약, 최단경로 이상으로 순회가 진행되는 것을 바라지 않는다면

bfs 함수 내에 탈출 조건 if(x===N-1 && y===M-1) break; 을 넣으면 된다.