[백준] - 14940 쉬운 최단거리 (node.js)

문제링크

풀이

BFS를 이용해 풀었다.

원래는 모든 점에서 시작해 BFS를 수행하는 식으로 구현했는데 너무 비효율적인 것 같아 찾아보니 시작점에서 뻗어나가는 식의 방법이 있어 해당 방법으로 문제를 풀었다.

코드

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

const [n, m] = nm.split(" ").map(Number);

let map = [];
for (let i = 0; i < n; i++) {
  map.push(input[i].split(" ").map(Number));
}

let location = Array.from(new Array(n), () => new Array(m).fill(-1));

let disx = [-1, 1, 0, 0];
let disy = [0, 0, -1, 1];

const dfs = (startx, starty) => {
  let q = [[startx, starty]];

  while (q.length !== 0) {
    const [x, y, dis] = q.shift();
    for (let i = 0; i < 4; i++) {
      let nextx = x + disx[i];
      let nexty = y + disy[i];
      if (
        nextx < n &&
        nextx >= 0 &&
        nexty < m &&
        nexty >= 0 &&
        location[nextx][nexty] === -1
      ) {
        q.push([nextx, nexty, dis + 1]);
        // 다음 location은 이전 + 1과 같음
        location[nextx][nexty] = location[x][y] + 1;
      }
    }
  }
};

let startx = 0;
let starty = 0;
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    if (map[i][j] === 2) { // 시작점 찾고
      startx = i;
      starty = j;
      location[i][j] = 0;
    }
    if (map[i][j] === 0) {
      location[i][j] = 0;
    }
  }
}

dfs(startx, starty);
for (let i = 0; i < n; i++) {
  console.log(location[i].join(" "));
}

문제를 풀 때 index 접근관련해서 더 꼼꼼하게 살펴봐야 할 것 같다.
BFS를 사용하는 문제의 경우 다 한번씩 TYPEERROR가 나는 느낌..