JavaScript 코딩테스트 - BFS with Queue

코딩 테스트 대비 저장용 포스트입니다.

BOJ 7576: 토마토 문제

• 최적화 하지 않은 코드여서 전체적인 사용법만 참고하기

"use strict";

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

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

  push(value) {
    const node = new Node(value);
    if (this.lenght === 0) {
      this.first = node;
      this.last = node;
    } else {
      this.last.next = node;
      this.last = node;
    }
    return ++this.lenght;
  }

  pop() {
    if (this.first === null) {
      return null;
    }
    if (this.first === this.last) {
      this.last = null;
    }
    const result = this.first.value;
    this.first = this.first.next;
    this.lenght--;
    return result;
  }
}

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
const [N, M] = input[0].split(" ").map(Number);
const arr = Array.from({ length: M }, () => []);
const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];
const queue = new Queue();
const checked = Array.from({ length: M }, () => Array.from({ length: N }, () => false));

let answer = 0;
let flag = true;

arr.map((_, idx, origin) => (origin[idx] = input[idx + 1].split(" ").map(Number)));

for (let i = 0; i < M; i++) {
  for (let j = 0; j < N; j++) {
    if (arr[i][j] === 1) {
      queue.push({ x: i, y: j, life: 0 });
      checked[i][j] = true;
    }
  }
}

while (queue.lenght) {
  const { x, y, life } = queue.pop();
  answer = Math.max(life, answer);
  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];

    if (nx < 0 || ny < 0 || M <= nx || N <= ny) {
      // OOB
      continue;
    }
    if (checked[nx][ny] || arr[nx][ny] !== 0) {
      // 제약조건
      continue;
    }
    checked[nx][ny] = true;
    arr[nx][ny] = 1;
    queue.push({ x: nx, y: ny, life: life + 1 });
  }
}

for (let i = 0; flag && i < M; i++) {
  for (let j = 0; flag && j < N; j++) {
    if (arr[i][j] === 0) {
      flag = false;
    }
  }
}

// 빈 칸이 남아있다면 -1, 없다면 걸린 시간 출력
console.log(flag ? answer : -1);