백준 7576 [nodejs] 토마토

const line = require("fs").readFileSync("/dev/stdin", "utf8");
let input = line.trim().split("\n");

const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
const [m, n] = input[0].split(" ").map(Number);

let tomatos = [];
let queue = [];
let zero = 0;
let cnt = 0;
minimumDate();

function minimumDate() {
//토마토밭을 만드는 for문
  for (let i = 1; i < n + 1; i++) {
    tomatos.push(input[i].split(" ").map(Number));
    for (let j = 0; j < tomatos[i - 1].length; j++) {
    	//1인 부분을 queue에 넣어 한번에 동작하게 함
      if (tomatos[i - 1][j] === 1) queue.push([i - 1, j]);
      //0인 부분을 모두 구해 놓는다.
      if (tomatos[i - 1][j] === 0) zero++;
    }
  }

  bfs(queue);
  zero !== 0 ? console.log(-1) : console.log(cnt - 2);
}

function bfs(queue) {
  //shift는 시간이 오래걸리므로 Cursor를 하나 둔다.
  let queueCursor = 0;
  while (queue.length > queueCursor) {
    const [x, y] = queue[queueCursor++];
    cnt = tomatos[x][y] + 1;
    for (let i in dx) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (check(nx, ny) && tomatos[nx][ny] === 0) {
        zero--;
        queue.push([nx, ny]);
        tomatos[nx][ny] = cnt;
      }
    }
  }
}

function check(x, y) {
  if (x > -1 && y > -1 && x < n && y < m) return true;
  return false;
}

 

 

ㅇㅇㅇㅇ토마토 같은 경우는 bfs에서 queue를 구현할 때 shift로 구현하게 되면 시간초과가 떳다.

그래서 queue의 값을 삭제하지않고 몇번째 있는지만 확인하여 진행하였다.

그리고 토마토 밭에 0이 남은 곳을 찾는 로직은 처음에 받을 때부터 0인 부분의 개수를 구한다음

0이 바뀔때마다 개수를 -1하면서 마지막에 개수가 0이라면 통과이고 아니면 -1로 나오게 하였다.