[백준] 7569 토마토 - javascript

📌 문제

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

📌 풀이

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

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

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

  push(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;
  }

  shift() {
    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;
  }
}

let [M, N, H] = input.shift().split(' ').map(Number);

let farm = Array.from({ length: H }, () =>
  Array.from({ length: N }, () => Array.from({ length: M }, () => 0))
);
let visited = Array.from({ length: H }, () =>
  Array.from({ length: N }, () => Array.from({ length: M }, () => 0))
);
let day = Array.from({ length: H }, () =>
  Array.from({ length: N }, () => Array.from({ length: M }, () => 0))
);

for (let i = 0; i < H; i++) {
  for (let j = 0; j < N; j++) {
    farm[i][j] = input.shift().split(' ').map(Number);
  }
}

const direction = [
  [0, 0, 1],
  [0, 0, -1],
  [0, 1, 0],
  [0, -1, 0],
  [1, 0, 0],
  [-1, 0, 0],
];
let queue = new Queue();
let leftTomato = 0;

for (let i = 0; i < H; i++) {
  for (let j = 0; j < N; j++) {
    for (let k = 0; k < M; k++) {
      if (farm[i][j][k] === 1) {
        visited[i][j][k] = 1;
        queue.push([i, j, k]);
      }
      if (farm[i][j][k] === 0) leftTomato++;
    }
  }
}

if (!leftTomato) console.log(0);
else {
  while (queue.length() > 0) {
    let [height, row, col] = queue.shift();

    for (let i = 0; i < direction.length; i++) {
      const [nheight, nrow, ncol] = [
        height + direction[i][0],
        row + direction[i][1],
        col + direction[i][2],
      ];

      if (
        nrow < 0 ||
        ncol < 0 ||
        nheight < 0 ||
        nrow >= N ||
        ncol >= M ||
        nheight >= H ||
        visited[nheight][nrow][ncol] ||
        farm[nheight][nrow][ncol] !== 0
      )
        continue;

      day[nheight][nrow][ncol] = day[height][row][col] + 1;
      leftTomato--;

      if (leftTomato == 0) {
        console.log(day[height][row][col] + 1);
        exit();
      }

      queue.push([nheight, nrow, ncol]);
      visited[nheight][nrow][ncol] = 1;
    }
  }
  console.log(-1);
}

✔ 알고리즘 : BFS + 구현

✔ 3차원 배열의 bfs 문제이다. 방향을 6개로 지정하여 탐색하였다.

✔ 전파가능한 토마토들은 queue에 집어넣고 탐색을 시작하였다.

✔ bfs탐색을 하며 남은 토마토의 개수가 0이 되면 모든 전파가 끝난 시점이므로 소요날짜를 출력해주었다.

✔ bfs 탐색이 끝났음에도 leftTomato가 0이 아닌 경우는 모두 익지 못하는 상황이므로 -1을 출력해주었다.

❗ 일반적인 bfs를 풀때 사용하는 let queue = [] 방식으로 제출을 했을 때 시간초과가 떴다. 구글링을 통해 직접 큐를 구현하여 제출해야 통과가 된다는 사실을 알게되어 큐를 구현하여 사용하였다.

✔ 난이도 : 백준 기준 골드 5