[백준] 2178번 - 미로 탐색

문제

https://www.acmicpc.net/problem/2178

 

// 입력
4 6
101111
101010
101011
111011

// 출력
15

 

풀이

BFS로 최단거리 찾기 문제.

맨 처음에 풀 때는 백트래킹을 안해줘서 시간제한에 걸렸는데, visitied로 방문했던 곳을 관리해 한번 갔던 곳은 다시 안 가게 했더니 통과했다.

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

const [N, M] = input[0].trim().split(' ').map(Number);
const maps = [];

for (let i = 1; i < input.length; i++) {
  maps.push(input[i].trim().split('').map(Number));
}

function solution(N, M, maps) {
  const dx = [1, -1, 0, 0];
  const dy = [0, 0, 1, -1];
  const visitied = Array.from({ length: N }, () => Array(M).fill(false));

  const queue = [];
  queue.push([0, 0, 1]);
  visitied[0][0] = true;

  while (queue.length > 0) {
    const [x, y, count] = queue.shift();
    if (x === M - 1 && y === N - 1) return count;

    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (
        nx >= 0 &&
        nx < M &&
        ny >= 0 &&
        ny < N &&
        !visitied[ny][nx] &&
        maps[ny][nx] === 1
      ) {
        queue.push([nx, ny, count + 1]);
        visitied[ny][nx] = true;
      }
    }
  }
}
console.log(solution(N, M, maps));