[BOJ] 7569 토마토 (node.js)

BOJ 문제 7569번의 풀이 과정을 작성한 게시글입니다.

 

링크

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

 

문제

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

 

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

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

 

풀이 과정

접근법 : BFS

기본적인 BFS 문제의 3차원 버전이다.

전체적인 풀이 과정은 익지 않은 토마토를 모두 큐에 넣고, 인접한 6방향으로 다음 위치를 설정한다.

큐에 넣을때는 날짜를 +1하고 익지않은 토마토를 모두 익게할 때까지 탐색해준다.

 

탐색이 다 끝났을 때 아직 익지 않은 토마토가 있다면 -1을 반환하고, 모두 익었다면 최대 일수를 정답으로 반환한다.

 

참고로 Javascript로 푼다면 Queue를 직접 구현해야 한다.

그 이유는 Queue의 shift 연산이 O(n)인데 토마토 상자가 최대 100x100x100 = 10^6이고, 최악의 경우 모든 칸을 방문해야 하므로 10^12의 시간복잡도가 발생하기 때문이다.

 

 

코드

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

const [M, N, H] = input.shift().split(" ").map(Number);
const tomato = [];

for (let i = 0; i < H; i++) {
  tomato.push(input.splice(0, N).map((x) => x.split(" ").map(Number)));
}

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  push(data) {
    const newNode = new Node(data);

    if (this.size === 0) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }

    this.tail = newNode;
    this.size++;
  }

  shift() {
    const data = this.head.data;

    this.head = this.head.next;
    this.size--;

    if (this.size === 0) {
      this.head = null;
      this.tail = null;
    }

    return data;
  }

  isEmpty() {
    return this.size === 0;
  }
}

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

const bfs = () => {
  let maxDay = 0;
  const queue = new Queue();

  for (let i = 0; i < H; i++) {
    for (let j = 0; j < N; j++) {
      for (let k = 0; k < M; k++) {
        if (tomato[i][j][k] === 1) {
          queue.push([i, j, k, 0]);
        }
      }
    }
  }

  while (!queue.isEmpty()) {
    const [cz, cx, cy, day] = queue.shift();

    maxDay = Math.max(maxDay, day);

    for (let i = 0; i < 6; i++) {
      const nx = cx + dx[i];
      const ny = cy + dy[i];
      const nz = cz + dz[i];

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

      if (tomato[nz][nx][ny] === 0) {
        tomato[nz][nx][ny] = 1;
        queue.push([nz, nx, ny, day + 1]);
      }
    }
  }

  for (let i = 0; i < H; i++) {
    for (let j = 0; j < N; j++) {
      for (let k = 0; k < M; k++) {
        if (!tomato[i][j][k]) {
          return -1;
        }
      }
    }
  }

  return maxDay;
};

console.log(bfs());

 

후기

bfs 문제를 풀 때 습관적으로 배열으로 queue를 구현하는 습관이 있다.

입력 크기를 확인하고 시간 초과가 발생할 것 같으면 연결리스트로 구현하자.