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

쉬운 최단거리(14940)

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다.
원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다

예제 입력 1

15 15

2 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 0 0 0 0 1

1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

1 1 1 1 1 1 1 1 1 1 0 1 0 0 0

1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예제 출력 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

11 12 13 14 15 16 17 18 19 20 0 0 0 0 25

12 13 14 15 16 17 18 19 20 21 0 29 28 27 26

13 14 15 16 17 18 19 20 21 22 0 30 0 0 0

14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

나의 Solution

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
let n = 0;
let m = 0;
let arr = [];
let dx = [-1, 1, 0, 0];
let dy = [0, 0, 1, -1];
let ch = [];
let queue = [];
rl.on("line", function (line) {
  input.push(line);
}).on("close", async function () {
  //n과 m을 입력받는다
  [n, m] = input[0].split(" ").map(Number);
  //방문 체크 배열을 만들기
  ch = Array.from(Array(n), () => Array(m).fill(0));
  //실제 거리를 이동한 배열을 따로 만들기
  //방문이 안된 곳은 -1이므로 -1로 초기화
  let dis = Array.from(Array(n), () => Array(m).fill(-1));
  for (let i = 1; i < input.length; i++) {
    arr.push(input[i].split(" ").map(Number));
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      //목적지를 기준으로 bfs를 돌단
      if (arr[i][j] === 2) {
        queue.push([i, j]);
        //dis는 갈 수있는 거리므로 0으로 초기화
        dis[i][j] = 0;
        ch[i][j] = 1;
      } else if (arr[i][j] === 0) {
        //0이면 0으로 초기화
        dis[i][j] = 0;
      }
    }
  }

  function bfs() {
    while (queue.length) {
      let [x, y] = queue.shift();
      for (let k = 0; k < 4; k++) {
        let nx = x + dx[k];
        let ny = y + dy[k];

        if (nx < 0 || ny < 0 || nx >= n || ny >= m || arr[nx][ny] !== 1 || ch[nx][ny] !== 0) continue;
        //거리 1증가
        dis[nx][ny] = dis[x][y] + 1;
        queue.push([nx, ny]);
        ch[nx][ny] = 1;
      }
    }
  }
  bfs();
  for (let i = 0; i < dis.length; i++) {
    console.log(dis[i].join(" "));
  }
});