[JavaScript][node.js] 백준 14940 쉬운 최단거리

문제

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

14940번: 쉬운 최단거리

자바스크립트(node.js)로 풀이했습니다.

풀이과정

• 1차 시도 실패 이유 - 메모리 초과
  • 갈 수 있는 모든 땅에 대해 bfs()를 다 돌림 -> visited는 bfs()를 호출할때마다 계속해서 할당 -> 메모리 초과
  • 이뿐만 아니라 최단거리는 직전 땅의 거리 정보를 이용해 구할 수 있으므로 각 땅이 아니라 전체를 bfs() 돌리는게 맞다

for (let i = 0; i < m; i++) {
  const line = [];
  for (let j = 0; j < n; j++) {
    const answer = maps[i][j] === 1 ? bfs([i, j]) : 0;
    line.push(answer);
  }
  console.log(line.join(' '));
}

• 2차 시도 실패 이유 - 2차원배열의 x, y 인덱스 반대로 착각
  • 예를 들어 maps[0][4] 는 좌표로 생각하면 (0, 4) 가 아닌 (4, 0) 이다

최종코드

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

const [n, m] = input[0].split(' ').map(Number);
const maps = input.slice(1).map((map) => map.split(' ').map(Number));

const visited = new Array(n).fill(0).map(() => new Array(m).fill(0));
const answer = new Array(n).fill(0).map(() => new Array(m).fill(0));

const getAnswer = () => {
  for (const i in maps) {
    for (const j in maps[i]) {
      if (maps[i][j] === 2) {
        return [+i, +j];
      }
    }
  }
};

const bfs = (start) => {
  const [y, x] = start;
  visited[y][x] = 1;

  const queue = [];
  queue.push(start);

  while (queue.length) {
    const cur = queue.shift();
    const [y, x] = cur;
    const d = [
      [0, -1],
      [0, 1],
      [-1, 0],
      [1, 0],
    ];

    for (const item of d) {
      const [dx, dy] = item;
      if (
        x + dx >= 0 &&
        x + dx < m &&
        y + dy >= 0 &&
        y + dy < n &&
        maps[y + dy][x + dx]
      ) {
        if (!visited[y + dy][x + dx]) {
          answer[y + dy][x + dx] = answer[y][x] + 1;
          queue.push([y + dy, x + dx]);
          visited[y + dy][x + dx] = 1;
        }
      }
    }
  }
};

const start = getAnswer();
bfs(start);
answer.forEach((line, i) => {
  line.forEach((spot, j) => {
    if (!spot && maps[i][j] === 1) {
      answer[i][j] = -1;
    }
  });
  console.log(line.join(' '));
});

인사이트

• JS 2차원 배열 선언과 동시에 0으로 초기화 하는 방법

const arr = new Array(높이).fill(0).map(() => new Array(너비).fill(0));