[백준/JS] 7569 토마토

문제

🧐 문제 풀이

기존 토마토 문제에서 이동 조건에 상,하 가 추가된 문제입니다!

따라서 이동 배열과 범위 조건을 변경해주면 되는 문제입니다.

queue.push([z, x, y, 0]);

큐를 담을 때도 z값을 함께 담아주면 됩니다.

let dx = [0, 0, 1, -1, 0, 0];
let dy = [1, -1, 0, 0, 0, 0];
let dz = [0, 0, 0, 0, 1, -1];

이동 방향을 x,y,z 로 세 가지로 나뉘어서 살펴보면 됩니다.

if (nz < 0 || nx < 0 || ny < 0 || nx >= M || ny >= N || nz >= H) continue;

범위를 벗어나는 조건에도 z방향을 보는 것을 추가해주면 됩니다.

나머지는 기존 bfs 방식과 동일합니다.

🚨 참고!

이 문제는 shift() 를 써서 풀면 시간초과가 나옵니다...
그러니 꼭 인덱스를 이용해서 푸세요!!!

📝 결과 코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./test.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

let input_idx = 0;
let [M, N, H] = input[input_idx].split(" ").map(Number);
input_idx++;

let dx = [0, 0, 1, -1, 0, 0];
let dy = [1, -1, 0, 0, 0, 0];
let dz = [0, 0, 0, 0, 1, -1];

let check_tomato = 0;

let queue = [];

let box = new Array(H).fill(null).map(() => []);

let visited = new Array(H).fill(null).map(() => []);

for (let h = 0; h < H; h++) {
  for (let y = 0; y < N; y++) {
    box[h].push(input[input_idx].split(" ").map(Number));
    input_idx++;
    visited[h].push(Array(M).fill(false));

    for (let x = 0; x < M; x++) {
      if (box[h][y][x] == 1) {
        queue.push([h, x, y, 0]);
        visited[h][y][x] = true;
        check_tomato++;
      } else if (box[h][y][x] == -1) {
        check_tomato++;
      }
    }
  }
}

let ans = 0;
let q_idx = 0;
const bfs = () => {
  while (q_idx !== queue.length) {
    let [z, x, y, cnt] = queue[q_idx];

    ans = Math.max(ans, cnt);

    for (let d = 0; d < 6; d++) {
      let nx = x + dx[d];
      let ny = y + dy[d];
      let nz = z + dz[d];

      if (nz < 0 || nx < 0 || ny < 0 || nx >= M || ny >= N || nz >= H) continue;

      if (visited[nz][ny][nx]) continue;

      if (box[nz][ny][nx] === 0) {
        queue.push([nz, nx, ny, cnt + 1]);
        visited[nz][ny][nx] = true;
        check_tomato++;
      }
    }

    q_idx++;
  }
};

if (check_tomato === N * M * H) {
  console.log(0);
} else {
  bfs();
  check_tomato === N * M * H ? console.log(ans) : console.log(-1);
}