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

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

7569번: 토마토

• 앞서 풀었던 백준 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, BOX_COUNT] = info.split(' ').map(val => +val);
const _input = input.map(row => row.split(' ').map(val => +val));
const dirs = [
  [0, 0, 1],
  [0, 0, -1],
  [0, 1, 0],
  [0, -1, 0],
  [1, 0, 0],
  [-1, 0, 0],
];

const boxes = (() => {
  const separated = [];

  while (_input.length) {
    separated.push(_input.splice(0, BOX_Y));
  }

  return separated;
})();

const queue = new Queue();

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

let daysNeeded = 0;

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

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

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

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

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

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

console.log(daysNeeded);

2-1. 풀이 설명

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

 

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

 

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

2-2. 회고

• 이번 문제가 조금 헷갈린다면 7576번 토마토 문제부터 풀어보는 것을 추천한다