[백준] 7569. 토마토 (자바스크립트/javascript/js/node.js/BFS/알고리즘)

 

지난번 풀었던 7576번 토마토 문제와 같은데 3차원 배열을 사용해서 풀어야 한다는 점이 추가된 문제이다.

처음에 이 문제를 봤을 때에는 지난번 토마토 문제도 어렵다고 느꼈었는데 이번엔 3차원이라니 정말 부담이 컸고 어려울 거라고 생각했다.

그러나 차근차근 생각해보니 인풋을 받아서 일단 3차원 배열에 토마토를 넣는 작업과, 상 하 좌 우 앞 뒤 인 경우를 따질 때 moveRow와 moveCol말고 moveBox도 하나 만들면 된다는 것만 생각해낸다면 해결할 수 있는 문제였다. 

알고리즘 연습을 얼마 해보지 않았을 때에는 조금만 응용이 되어도 잘 풀지 못하는 것 같아서 과연 내가 실력이 늘고 있는건가 회의감도 들었었는데, 그래도 포기하지 않고 꾸준히 연습을 하니 실력이 상승되는 것 같다.

점점 백준에서 예전엔 풀지도 못했던 난이도의 문제를 이제는 해결할 수 있고, 또 점점 해결하는 속도도 빨라지는 걸 보면서 헛되이 공부한 건 아닌 것 같다는 생각에 뿌듯함이 생긴다. 점점 머리를 쓸 줄 알고 생각하는 힘이 길러지는 것 같아서 뿌듯하다. 앞으로 더 어려운 문제가 나오더라도 포기하지만 않는다면 할 수 있다는 생각을 가질 것이다!

 

let fs = require("fs");
let input = fs.readFileSync("예제.txt").toString().split("\n");
input[0] = input[0].split(" ");
const Row = Number(input[0][1]);
const Column = Number(input[0][0]);
const Box = Number(input[0][2]);
input.shift();
input = input.map((element) => element.trim().split(" "));
const tomato = Array.from(new Array(Box), () => new Array());

for (let b = 0; b < Box; b++) {
  const startIndex = b * Row;
  for (let i = startIndex; i < startIndex + Row; i++) {
    tomato[b].push(input[i]);
  }
}
const rangeCheck = (box, row, col) => {
  if (
    box >= 0 &&
    box < Box &&
    row >= 0 &&
    row < Row &&
    col >= 0 &&
    col < Column
  ) {
    return true;
  }
  return false;
};
const BFS = (queue) => {
  let result;
  let number = 0;
  while (number !== queue.length) {
    const b = queue[number][0];
    const r = queue[number][1];
    const c = queue[number][2];
    // console.log(`b: ${b}, r : ${r}, c: ${c}`);
    for (let d = 0; d < 6; d++) {
      const nextBox = b + moveBox[d];
      const nextRow = r + moveRow[d];
      const nextCol = c + moveCol[d];
      if (
        rangeCheck(nextBox, nextRow, nextCol) &&
        ripeTomato[nextBox][nextRow][nextCol] === 0 &&
        Number(tomato[nextBox][nextRow][nextCol]) === 0
      ) {
        queue.push([nextBox, nextRow, nextCol]);
        ripeTomato[nextBox][nextRow][nextCol] = ripeTomato[b][r][c] + 1;
        result = ripeTomato[nextBox][nextRow][nextCol];
      }
    }
    number++;
  }
  return result - 1;
};

const queue = []; // 큐 : [ [box, row, column], [box, row, column]]... 큐에는 익은 토마토가 들어갈 예정이다.
const ripeTomato = Array.from(new Array(Box), () =>
  Array.from(new Array(Row), () => new Array(Column).fill(0))
);
const moveBox = [0, 0, 0, 0, -1, 1]; // 동 서 남 북 앞 뒤
const moveRow = [0, 0, 1, -1, 0, 0]; // 동 서 남 북 앞 뒤
const moveCol = [1, -1, 0, 0, 0, 0]; // 동 서 남 북 앞 뒤

// 초벌 작업 끝

let zero = false;
for (let b = 0; b < Box; b++) {
  for (let r = 0; r < Row; r++) {
    for (let c = 0; c < Column; c++) {
      if (Number(tomato[b][r][c]) === 1) {
        queue.push([b, r, c]);
        ripeTomato[b][r][c] = 1;
      }
      if (Number(tomato[b][r][c]) === -1) {
        ripeTomato[b][r][c] = -1;
      }
      if (Number(tomato[b][r][c]) === 0) {
        zero = true;
      }
    }
  }
}
let answer;

if (!zero) {
  answer = 0;
} else {
  answer = BFS(queue);

  for (let b = 0; b < Box; b++) {
    for (let r = 0; r < Row; r++) {
      for (let c = 0; c < Column; c++) {
        if (ripeTomato[b][r][c] === 0) {
          answer = -1;
          break;
        }
      }
    }
  }
}
console.log(answer);