[알고리즘 연습] 백준 2636 (치즈, 자바스크립트)

문제

2636번: 치즈

---

풀이

• 판의 가장자리('X')에는 치즈가 놓여져있지 않기 때문에 모든 BFS의 시작점을 (0, 0)으로 지정한다.
• 매 BFS 수행시 바깥 부분('공기')와 접촉되어 있는 모든 치즈를 찾아 판에서 제거한다.
• 판에 치즈가 모두 녹아 없어질 때까지 BFS를 수행하며 시간('time')을 증가시킨다.
• 제거할 치즈가 존재할 경우 제거되는 치즈의 개수('cnt')를 업데이트 해준다.

소스 코드

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 filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const [H, W] = input[0].split(" ").map(Number);
const board = Array.from({ length: H }, () => Array(W));
const dir = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];
let time = 0;
let cnt = 0;

for (let i = 1; i <= H; i++) {
  const arr = input[i].split(" ").map(Number);
  for (let j = 0; j < W; j++) {
    board[i - 1][j] = arr[j];
  }
}

function bfs() {
  const queue = new Queue();
  const visited = Array.from({ length: H }, () => Array(W).fill(false));
  const nodes = [];
  queue.push([0, 0]);
  visited[0][0] = true;

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

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

      if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
      if (visited[nx][ny]) continue;
      if (board[nx][ny] === 1) {
        nodes.push([nx, ny]);
        visited[nx][ny] = true;
        continue;
      }

      queue.push([nx, ny]);
      visited[nx][ny] = true;
    }
  }

  for (const [x, y] of nodes) board[x][y] = 0;

  if (!nodes.length) return true;

  cnt = nodes.length;
  return false;
}

while (true) {
  if (bfs()) break;

  time += 1;
}

console.log(time + "\n" + cnt);