[백준] 14940번: 쉬운 최단거리 - Node.js (자바스크립트)

1. 문제 ㅡ 14940번: 쉬운 최단거리 (난이도: Silver I)

14940번: 쉬운 최단거리

2. 풀이 ㅡ Node.js (자바스크립트)

const getDistances = () => {
  const [info, ...input] = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');

  const [Y, X] = info.split(' ').map(val => +val);
  const board = input.map(row => row.split(' ').map(val => (val === '0' ? 0 : val === '2' ? 2 : -1)));
  const visited = Array.from({ length: Y }).map(() => Array.from({ length: X }, () => false));
  
  const dirs = [[0, 1], [0, -1], [-1, 0], [1, 0]];
  const queue = [];

  for (let y = 0; y < board.length; y++) {
    for (let x = 0; x < board[y].length; x++) {
      if (board[y][x] !== 2) continue;

      queue.push([x, y, 0]);
      break;
    }
  }

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

    board[y][x] = time;

    for (let i = 0; i < 4; i++) {
      const xPos = x + dirs[i][0];
      const yPos = y + dirs[i][1];

      if (xPos < 0 || yPos < 0 || xPos >= X || yPos >= Y || board[yPos][xPos] === 0 || visited[yPos][xPos]) continue;

      visited[yPos][xPos] = true;

      board[yPos][xPos] = time + 1;
      queue.push([xPos, yPos, time + 1]);
    }
  }

  return board.map(row => row.join(' ')).join('\n');
};

console.log(getDistances());

 

2-1. 풀이 설명

각 칸에서 좌우상하로만 이동해서 값이 2인 도착점까지 몇 번 이동해야 갈 수 있는지 확인하는 문제다. 반대로, 풀이할 때는 도착점에서 BFS 탐색을 시작해서 각 칸까지의 최단거리를 찾으면 더 쉽다. 

 

도착점의 x, y 좌표와 함께 거리를 나타내는 0과 함께  queue에 넣어주고 BFS 탐색을 시작한다.

1. 탐색 중인 칸과 인접한 칸을 찾고, 값이 0, 즉 갈 수 없는 칸이거나, 이미 확인한 칸이면 queue에 넣지 않는다. 
2. 탐색해야 하는 칸인 경우 queue에 해당 칸의 x, y 좌표와 함께 거리 + 1을 한 값을 넣어주고, 해당 x, y 좌표에 해당하는 visited 배열의 값을 true로 변경해줘 다시 queue에 들어가는 일이 없도록 한다.