[알고리즘/백준/14940] 쉬운 최단거리(BFS, Nodejs)

문제

---

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

14940번: 쉬운 최단거리

 

풀이

---

class Queue {
  constructor() {
    this.data = [];
    this.head = 0;
    this.tail = 0;
  }
  push(item) {
    this.data[this.tail++] = item;
  }
  pop() {
    this.head++;
  }
  front() {
    return this.data[this.head];
  }
  rear() {
    return this.data[this.tail - 1];
  }
  isEmpty() {
    return this.head === this.tail;
  }
  size() {
    return Math.abs(this.head - this.tail);
  }
}
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [n, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M] = n.split(" ").map(Number);
const dir = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];
const map = arr.map((row) => row.split(" ").map(Number));
const q = new Queue();
const ch = Array.from({ length: N }, () => Array(M).fill(0));
const dis = Array.from({ length: N }, () => Array(M).fill(0));

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (map[i][j] === 2) {
      q.push([i, j]);
      ch[i][j] = 1;
      dis[i][j] = 0;

      while (!q.isEmpty()) {
        const [x, y] = q.front();
        q.pop();

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

          if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

          if (map[nx][ny] === 1 && ch[nx][ny] === 0) {
            dis[nx][ny] = dis[x][y] + 1;
            ch[nx][ny] = 1;
            q.push([nx, ny]);
          }
        }
      }
    }
  }
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (map[i][j] === 1 && ch[i][j] === 0) dis[i][j] = -1;
  }
}

console.log(dis.map((row) => row.join(" ")).join("\n"));

 

---

 

시도 

처음에 아래와 같이 각 지점에서 목표 지점까지의 거리라고 문제 그대로 생각하고 2중 for문 안에서 값이 1인 경우 2까지의 거리를 저장하도록 문제를 풀었다. 답은 나왔지만 백준에서 메모리 초과가 나왔다.

const [N, M] = n.split(" ").map(Number);
const dir = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];
const map = arr.map((row) => row.split(" ").map(Number));
const answer = Array.from({ length: N }, () => Array(M).fill(0));

// for문에서 각 노드를 돌면서 목표지점까지 거리 출력
// 1. 1인 경우 -> 갈 수 있으면 거리 출력, 아니면 -1
// 2. 0인 경우 0 -> 그냥 리턴

const BFS = (i, j) => {
  const q = new Queue();
  const ch = Array.from({ length: N }, () => Array(M).fill(0));
  const dis = Array.from({ length: N }, () => Array(M).fill(0));

  dis[i][j] = 0;
  q.push([i, j]);
  ch[i][j] = 1;

  while (!q.isEmpty()) {
    const [x, y] = q.front();
    q.pop();

    for (let k = 0; k < 4; k++) {
      const nx = x + dir[k][0];
      const ny = y + dir[k][1];

      if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

      // 도착지
      if (map[nx][ny] === 2) {
        return dis[x][y] + 1;
      }

      if (ch[nx][ny] === 0 && map[nx][ny] === 1) {
        q.push([nx, ny]);
        ch[nx][ny] = 1;
        dis[nx][ny] = dis[x][y] + 1;
      }
    }
  }

  return -1;
};

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (map[i][j] === 0 || map[i][j] === 2) continue;

    if (map[i][j] === 1) answer[i][j] = BFS(i, j);
  }
}

console.log(answer.map((row) => row.join(" ")).join("\n"));

 

해결 방법은 풀이와 같이 반대로 목적지인 2에서 값이 1인 지점까지의 거리를 구하는 것이다. 그렇게 하면 bfs를 값이 1인 지점마다 돌지 않고 한 번만 돌게 된다. 그리고 출력하기 전 값이 1이면서 방문하지 않은 지점인 경우 dis배열에서 해당 지점의 값을 -1로 변경한다.

 

문제를 풀기 위한 다양한 방법을 생각해보고 가장 효율적인 답을 생각하도록 해야겠다.