백준 7569 토마토 | JavaScript 3차원 BFS

https://www.acmicpc.net/problem/7569

3차원이라서 헷갈렸던..😵

시작

1일

2일

3일

4일

입력받은 토마토 정보 == 방문 체크 배열이라고 생각하면 일반적인 bfs 문제에서 조금만 변형하여 풀 수 있다!

while (!q.empty()) {
    const [z, y, x, cnt] = q.pop();

    for (let i = 0; i < 6; i++) {
      const nextX = x + dx[i];
      const nextY = y + dy[i];
      const nextZ = z + dz[i];

      if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N || nextZ < 0 || nextZ >= H) continue;

      if (tomato[nextZ][nextY][nextX] == 0) {
        tomato[nextZ][nextY][nextX] = 1;
        q.push([nextZ, nextY, nextX, cnt + 1]);

      }
      console.log(tomato);
    }
  }

최단거리를 찾는 bfs에 방향을 하나 추가해주면 된다 !

  for (let h = 0; h < H; h++) {
    for (let n = 0; n < N; n++) {
      for (let m = 0; m < M; m++) {
        if (tomato[h][n][m] === 1)
          q.push([h, n, m, 0]);
      }
    }
  }

처음에 익어있는 토마토를 모두 큐에 넣고 bfs를 돌면 된다.

안 익은 토마토가 더이상 없으면 while문을 탈출해야하는데, while문의 매반복마다 완전탐색을 하며 체크하기에는 효율이 좋지 않다.

미리 안 익은 토마토의 수를 세고, 토마토가 익을 때마다 값을 감소시키면 된다.

  for (let h = 0; h < H; h++) {
    for (let n = 0; n < N; n++) {
      for (let m = 0; m < M; m++) {
        if (tomato[h][n][m] === 1) {
          q.push([h, n, m, 0]);
        } else if (tomato[h][n][m] === 0) {
          unriped++;
        }
      }
    }
  }

전체 코드

const fs = require("fs");
const input = fs.readFileSync(0, "utf-8").trim().split("\n");

const [M, N, H] = input[0].split(" ").map(Number);
let tomato = [];
let idx = 1;

for (let h = 0; h < H; h++) {
  let layer = [];
  for (let n = 0; n < N; n++) {
    layer.push(input[idx++].split(" ").map(Number));
  }
  tomato.push(layer);
}

class Queue {
  constructor() {
    this.queue = {};
    this.start = 0;
    this.end = 0;
  }

  push(x) {
    this.queue[this.end++] = x;
  }

  pop() {
    const value = this.queue[this.start];
    delete this.queue[this.start++];
    return value;
  }

  empty() {
    return this.end === this.start;
  }
}

function solution() {
  let q = new Queue();
  let day = 0;
  let unriped = 0;

  for (let h = 0; h < H; h++) {
    for (let n = 0; n < N; n++) {
      for (let m = 0; m < M; m++) {
        if (tomato[h][n][m] === 1) {
          q.push([h, n, m, 0]);
        } else if (tomato[h][n][m] === 0) {
          unriped++;
        }
      }
    }
  }

  // 위, 아래, 동, 서, 남, 북
  const dx = [0, 0, 1, -1, 0, 0];
  const dy = [0, 0, 0, 0, -1, 1];
  const dz = [1, -1, 0, 0, 0, 0];

  while (!q.empty()) {
    const [z, y, x, cnt] = q.pop();

    for (let i = 0; i < 6; i++) {
      const nextX = x + dx[i];
      const nextY = y + dy[i];
      const nextZ = z + dz[i];

      if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N || nextZ < 0 || nextZ >= H) continue;

      if (tomato[nextZ][nextY][nextX] == 0) {
        tomato[nextZ][nextY][nextX] = 1;
        unriped--;
        q.push([nextZ, nextY, nextX, cnt + 1]);

        if (unriped === 0) return console.log(cnt + 1);
      }
      console.log(tomato);
    }
    day = cnt;
  }
  return unriped === 0 ? console.log(day) : console.log(-1);
}

solution();