[백준/JavaScript] 토마토(7569)

문제

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

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

[ 입력 ]

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

 

[ 출력 ]

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

풀이

• 토마토를 3차원 배열에 배치하고 상하좌우위아래를 이동하면서 토마토를 익혀준다
• bfs로 풀이
• ⚠️ 입력 받을 때 input의 index로 접근해서 3차원 배열로 만들어주려고 했는데, 뭔가 잘못했는지 계속 에러가 나서 shift()로 바꿔줬다
• 토마토의 위치와 현재 날짜가 얼마나 지났는지를 저장할 class Tomato를 따로 만들어서 사용했다

// 백준 - 토마토(7569)
class Tomato {
  constructor(z, x, y, day) {
    this.z = z;
    this.x = x;
    this.y = y;
    this.day = day;
  }
}

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

const solution = ( input ) => {
  const [ M, N, H ] = input.shift().split(" ").map(el => parseInt(el));
  let tomatoes = [];
  
  for(let i = 0; i < H; i++) {
    let box = [];
    for(let j = 0; j < N; j++) {
      box.push(input.shift().split(" ").map(el => parseInt(el)));
    }

    tomatoes.push(box);
  }

  const queue = [];
  let remainCnt = 0; // 안 익은 토마토 수
  for(let i = 0; i < H; i++) {
    for(let j = 0; j < N; j++) {
      for(let k = 0; k < M; k++) {
        if (tomatoes[i][j][k] === 1)
          queue.push(new Tomato(i, j, k, 0));
        else if (tomatoes[i][j][k] === 0)
          remainCnt++;
      }
    }
  }

  let index = 0;
  let answer = 0;
  while(queue.length > index) {
    const current = queue[index++];

    for(let i = 0; i < 6; i++) {
      const moveZ = current.z + dz[i];
      const moveX = current.x + dx[i];
      const moveY = current.y + dy[i];

      if(moveX < 0 || moveX >= N || moveY < 0 || moveY >= M || moveZ < 0 || moveZ >= H) continue;

      if(tomatoes[moveZ][moveX][moveY] === 0) {
        tomatoes[moveZ][moveX][moveY] = 1;
        queue.push(new Tomato(moveZ, moveX, moveY, current.day + 1));
        remainCnt--;
      }
    }

    answer = current.day;
  }

  // 남은 토마토가 있는지 체크
  if(remainCnt == 0) console.log(answer);
  else console.log(-1);
}

/*
테스트용: __dirname + '/input.txt'
제출용: '/dev/stdin'
*/
const fs = require('fs');
const input = fs.readFileSync(__dirname + '/input.txt').toString().trim().split('\n');

solution(input);