[백준/7576/node.js] 토마토

위 예제에서 익은 토마토의 위치가 [3,5]이고, 여기서 하루가 지나면 인접한 위치인 [2,5],[3,4]에 있는 토마토가 익는다.

따라서

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

[3,5]

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 1

[3,5] -> [2,5], [3,4]로 이동,

0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 1 1 1

[2,5] -> [1,5], [2,4]로 이동,
[3,4] -> [3,3]으로 이동한다.

따라서 먼저 들어간 데이터가 먼저 나가는 queue 자료구조를 이용한 BFS를 쓰면 된다는 것을 알게되었다!

처음에 shift() 메서드를 사용했었는데 시간초과가 나서 질문 게시판을 봤더니

이런식으로 구현하는 방법이 있다고 해서 2번째 방법을 쓰기로 했다!

shift() 메서드는 맨 앞에 있는 값을 제거한 후에 기존에 배열에 있던 모든 요소를 한 자리씩 왼쪽으로 이동시켜야 하기 때문에 시간 복잡도가 O(n) 이라고 한다.

shift 메서드가 생각보다 오래 걸리는 메서드였다...
무지성으로 사용하고 있던 나 반성 🫠

👩‍💻 전체 코드

// 인풋 값 입력 받는 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

let [M, N] = input.shift().split(" ").map(Number);

let arr = [];

input.forEach((v) => arr.push(v.split(" ").map(Number)));

// 상하좌우 방향 
const directionX = [-1, 0, 1, 0];
const directionY = [0, 1, 0, -1];

const queue = [];

let date = 0;

let pointer = 0;

function bfs() {
  while (queue.length !== 0) {
    if (pointer + 1 > queue.length) {
      return;
    }  // pointer가 queue의 길이를 넘어가면 return
    let { x: curX, y: curY, date: curDate } = queue[pointer++];
    date = curDate; // queue에 있는 date로 갱신
    for (let i = 0; i < 4; i++) {
      let nextX = curX + directionX[i];
      let nextY = curY + directionY[i];
      if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) continue;
      if (arr[nextX][nextY] === 0) {
        arr[nextX][nextY] = 1;  // 익은 토마토로 바꿔줌
        queue.push({ x: nextX, y: nextY, date: curDate + 1 }); 
        // queue에 다음 좌표와 마지막 queue의 date에 하루를 추가해서 넣어줌
      }
    }
  }
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (arr[i][j] <= 0) continue;
    queue.push({ x: i, y: j, date: 0 });
  }
} // 제일 처음에 익은 토마토들을 queue에 넣어줌

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    bfs();
  }
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (arr[i][j] === 0) {   // 익지 않은 토마토가 있다면
      console.log(-1);       // -1 출력
      process.exit();
    }
  }
}

console.log(date);