백준 2638번 치즈 JavaScript 풀이 [BFS]

백준 2638번 치즈 문제를 자바스크립트로 BFS 알고리즘을 이용해서 풀어보았다. 

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

 

let fs = require("fs");
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const element = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return element;
  }
  getLength() {
    return this.tail - this.head;
  }
}

let [n, m] = input[0].split(' ').map(Number);
let graph = [];
for (let i=1; i<=n; i++) graph.push(input[i].split(' ').map(Number))

function bfs(graph) {
  let visited = new Array(n).fill().map(_ => new Array(m).fill(0));
  queue = new Queue;
  queue.enqueue([0, 0]);
  visited[0][0] = 1;
  
  while (queue.getLength() != 0) {
    let [x, y] = queue.dequeue();
  
    for (let dx of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      let nx = x + dx[0];
      let ny = y + dx[1];
  
      if (0 <= nx && nx <= n-1 && 0 <= ny && ny <= m-1) {
        if (visited[nx][ny] == 0) {
          if (graph[nx][ny] >= 1) graph[nx][ny] += 1;
          else {
            queue.enqueue([nx, ny])
            visited[nx][ny] = 1;
          }
        }
      }
    }
  }
}

let remain;
let count = 0;

while (true) {
  bfs(graph)
  remain = 0;
  for (let i=0; i<n; i++) {
    for (let j=0; j<m; j++) {
      remain += graph[i][j];
      if (graph[i][j] >= 3) graph[i][j] = 0;
      else if (graph[i][j] == 2) graph[i][j] = 1;
    }
  }
  if (remain == 0) break;
  count++;
}
console.log(count)