[백준] 7576번: 토마토 - Node.js (자바스크립트)

1. 문제 ㅡ 7576번: 토마토 (난이도: Gold V)

7576번: 토마토

2. 풀이 ㅡ Node.js (자바스크립트)

class Queue {
  constructor() {
    this.q = [];
    this.head = 0;
    this.tail = 0;
  }

  push(item) {
    this.q[this.tail++] = item;
  }

  shift() {
    this.head++;
  }

  front() {
    return this.q[this.head];
  }

  isEmpty() {
    return this.head === this.tail;
  }
}

const [info, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [BOX_X, BOX_Y] = info.split(' ').map(val => +val);
const box = input.map(row => row.split(' ').map(val => +val));
const dirs = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];

const queue = new Queue();

for (let y = 0; y < BOX_Y; y++) {
  for (let x = 0; x < BOX_X; x++) {
    if (box[y][x] === 1) queue.push([x, y, 0]);
  }
}

let daysNeeded = 0;

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

  dirs.forEach(dir => {
    const xPos = x + dir[0];
    const yPos = y + dir[1];

    if (xPos < 0 || yPos < 0 || xPos >= BOX_X || yPos >= BOX_Y || box[yPos][xPos] !== 0) return;

    box[yPos][xPos] = 1;
    queue.push([xPos, yPos, days + 1]);

    daysNeeded = daysNeeded < days + 1 ? days + 1 : daysNeeded;
  });
}

box.forEach(row => {
  if (row.includes(0)) daysNeeded = -1;
});

console.log(daysNeeded);

 

2-1. 풀이 설명

기존에 접해봤던 BFS 문제들은 주로 하나의 시작점을 queue에 넣어두고 탐색을 시작했지만, 이번 문제는 Multi Source BFS 유형의 문제다. 즉, 입력값으로 받은 토마토 박스에 이미 익은 토마토가 여러개 존재할 수도 있다.

 

토마토 박스를 순회하면서 1, 즉 익은 토마토를 발견하면 해당 위치의 x, y 좌표와 함께 시간을 나.타내는 0을 배열에 담아 queue에 넣어줬다. 생성된 queue를 BFS 탐색하면서 1 좌우상하에 0, 즉 익지 않은 토마토가 있는 경우 1로 변경해주고, queue에 해당 좌표와 시간 + 1을 배열에 담아 넣어줬다. 

 

while문이 종료된 후 박스에 익지 않은 토마토가 남아 있으면 박스에 있는 모든 토마토가 익을 수 없다고 판단하여 누적된 시간 정보를 -1로 변경해주었다.

2-2. 회고

• 처음에는 Queue 클래스를 직접 구현하지 않고 배열 메서드를 사용해서 풀었더니 시간 초과. shift 메서드를 반복적으로 사용하는 것이 아마 원인이었을 것이다. 직접 큐를 구현해서 사용하고 나니 바로 통과되었다.