[boj] 7569. 토마토 (node.js)

문제 요약

[boj] 7569. 토마토 (node.js)

풀이

• 간만에 푼 BFS 문제! 최단 시간을 구해야 하므로 BFS로 탐색하는 문제다. 익은 토마토부터 출발하여 모든 익지 않은 토마토들까지 도달해야 한다.
• 로직은 한큐에 떠올려서 맞게 풀었는데, 구현이나 디버깅이 생각보다 오래 걸렸다.
• 아무리 생각해도 틀린 로직이 없는 것 같은데 시간초과가 자꾸 나서 구글링했더니, 내장 메서드의 느린 속도로 인해 시간초과가 발생하는 경우였다. 미리 정의해둔 Queue 클래스를 가져다 넣었더니 맞았다!
• 이렇게 node.js로 풀 때마다 코드 풀이 로직은 알아도, 구현에서 막히는 일 때문에 시간이 너무 많이 낭비되는 걸 느낀다. T-T
• 특히 queue를 활용하는 알고리즘을 쓰게 되는 경우 매번 push()와 shift() 메서드를 써서 풀리는 경우와 아닌 경우를 의심하게 되는데, 매번 스트레스받기보다 차라리! 큐 구현을 정말 여러 번 연습해서 아예 자동반사로 튀어나올 수 있도록 해 둬야겠다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

class Node {
  constructor(data) {
    this.value = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  enqueue(val) {
    let node = new Node(val);
    if (!this.first) {
      this.first = node;
      this.last = node;
    } else {
      this.last.next = node;
      this.last = node;
    }
    return ++this.size;
  }

  dequeue() {
    if (!this.first) return null;
    let node = this.first;
    if (this.first == this.last) this.last = null;
    this.first = this.first.next;
    this.size--;
    return node.value;
  }

  length() {
    return this.size;
  }
}

const dir = [
  [0, 0, 1],
  [0, 0, -1],
  [0, 1, 0],
  [0, -1, 0],
  [1, 0, 0],
  [-1, 0, 0],
];

const solution = () => {
  let [M, N, H] = input().split(" ").map(Number);
  let arr = [];
  let queue = new Queue();
  let left = 0;
  let date = [];
  let visited = [];
  for (let i = 0; i < N; i++) {
    arr[i] = [];
    date[i] = [];
    visited[i] = [];
    for (let j = 0; j < M; j++) {
      arr[i][j] = [];
      date[i][j] = [];
      visited[i][j] = [];
    }
  }
  for (let i = 0; i < N * H; i++) {
    let line = input().trim().split(" ").map(Number);
    let row = i % N;
    let hei = Math.floor(i / N);
    line.forEach((item, col) => {
      arr[row][col].push(item);
      if (item == -1) return;
      else if (item == 0) left++;
      else if (item == 1) {
        visited[row][col][hei] = 1;
        queue.enqueue([row, col, hei]);
        date[row][col][hei] = 0;
      }
    });
  }
  if (left == 0) return 0;
  return bfs();

  function bfs() {
    while (queue.length() > 0) {
      let [row, col, height] = queue.dequeue();
      visited[row][col][height] = 1;
      for (let i = 0; i < dir.length; i++) {
        let nrow = row + dir[i][0];
        let ncol = col + dir[i][1];
        let nheight = height + dir[i][2];
        if (nrow < 0 || ncol < 0 || nheight < 0) continue;
        if (nrow >= N || ncol >= M || nheight >= H) continue;
        if (visited[nrow][ncol][nheight]) continue;
        if (arr[nrow][ncol][nheight] != 0) continue;
        // --- if successfully arrived ----
        let min = date[row][col][height] + 1;
        date[nrow][ncol][nheight] = min;
        left--;
        if (left == 0) return min; // final tomato
        queue.enqueue([nrow, ncol, nheight]);
        visited[nrow][ncol][nheight] = 1;
      }
    }
    return -1;
  }
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  let result = solution();
  console.log(result);
  process.exit();
});