Node.js)백준 2638번: 치즈

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

2638번: 치즈

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

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(item) {
    const node = new Node(item);
    if (this.head == null) {
      this.head = node;
    } else {
      this.tail.next = node;
    }

    this.tail = node;
    this.length += 1;
  }

  pop() {
    const popItem = this.head;
    this.head = this.head.next;
    this.length -= 1;
    return popItem.item;
  }
}

const fs = require("fs");
const input = fs
  .readFileSync("./dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

let [N, M] = input.shift();
N += 2;
M += 2;

const board = input.map((v) => {
  v.unshift(0);
  v.push(0);
  return v;
});
board.unshift(new Array(M).fill(0));
board.push(new Array(M).fill(0));
board[0][0] = -1;
const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];
let checked = Array.from(Array(N), () => Array(M).fill(false));

// 공기랑 닿은 치즈& 공기 체크

const checkCheese = (a, b) => {
  checked[a][b] = true;
  board[a][b] = -1
  let q = new Queue();
  q.push([a, b]);
  const cheese = [];
  while (q.length > 0) {
    const [x, y] = q.pop();
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (nx >= 0 && nx < N && ny >= 0 && ny < M && !checked[nx][ny]) {
        if (board[nx][ny] == 0) {
          q.push([nx, ny]);
          board[nx][ny] = -1;
        } else {
          cheese.push([nx, ny]);
        }
        checked[nx][ny] = true;
      }
    }
  }
  return cheese;
};

const checkMelting = (arr) => {
  const melt = [];
  const notYet = [];
  arr.forEach((v) => {
    const [x, y] = v;
    let cnt = 0;
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
      if (board[nx][ny] == -1) cnt++;
    }
    if (cnt >= 2) {
      melt.push([x, y]);
    } else {
      notYet.push([x, y]);
    }
  });

  return [melt, notYet];
};

const goMelt = (arr) => {
  let newCheese = [];
  arr.forEach((v) => {
    const [x, y] = v;
    board[x][y] = -1;
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
        if (board[nx][ny] == 0) {
          newCheese = newCheese.concat(checkCheese(nx, ny));
        }
        if (board[nx][ny] == 1 && !checked[nx][ny]) {
          checked[nx][ny] = true;
          newCheese.push([nx, ny]);
        }
      }
    }
  });
  return newCheese;
};

const solve = () => {
  let time = 0;
  let cheese = checkCheese(0, 0);

  while (cheese.length > 0) {
    time++;
    const [melt, notYet] = checkMelting(cheese);
    const newCheese = goMelt(melt);
    cheese = notYet.concat(newCheese);
  }
  return time;
};

console.log(solve());