[BOJ] 7569: 토마토 / JS

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

 

 

 

 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [m, n, h] = input.shift().split(' ').map(Number);
const map = [];
let temp = [];
for (let i = 0; i < h; i++) {
  for (let j = 0; j < n; j++)
    temp.push(...input.shift().split(' ').map(Number));
  map.push(temp);
  temp = [];
}

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

let leftTomato = 0;

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

class Queue {
  constructor() {
    this.head = new Node([]);
    this.tail = this.head;
    this.size = 0;
  }

  push(data) {
    const node = new Node(data);
    this.tail.next = node;
    this.tail = node;
    this.size++;
  }

  shift() {
    if (this.size === 0) return;
    const node = this.head.next;
    if (node === this.tail) this.tail = this.head;
    this.head.next = node.next;
    this.size--;
    return node.data;
  }

  getSize() {
    return this.size;
  }
}

const queue = new Queue();

function isRange(k, x, y) {
  return k >= 0 && k < h && x >= 0 && x < n && y >= 0 && y < m;
}

function bfs() {
  let day = 0;
  while (queue.getSize()) {
    const [h, x, y, d] = queue.shift();
    day = d;
    for (let k = 0; k < 6; k++) {
      const nh = h + dh[k];
      const nx = x + dx[k];
      const ny = y + dy[k];
      if (!isRange(nh, nx, ny) || map[nh][nx * m + ny] !== 0) continue;
      queue.push([nh, nx, ny, d + 1]);
      map[nh][nx * m + ny] = 1;
      leftTomato--;
    }
  }
  return leftTomato === 0 ? day : -1;
}

function solution() {
  for (let k = 0; k < h; k++) {
    for (let i = 0; i < n; i++)
      for (let j = 0; j < m; j++) {
        if (map[k][i * m + j] === 1) queue.push([k, i, j, 0]);
        else if (map[k][i * m + j] === 0) leftTomato++;
      }
  }
  console.log(leftTomato === 0 ? 0 : bfs());
}
solution();

익은 토마토로부터 안 익은 토마토까지의 최단 거리를 구하면 되기 때문에 BFS를 사용해서 해결했다.

"7569: 토마토"는 다른 문제들과는 달리 3차원 문제다.

따라서 배열을 3차원으로 구현하고 해결해야 한다.

나는 좀 더 문제를 단순화 시키고자 토마토 상자 하나를 n * m크기의 1개의 배열로 표현했다.

 

3차원 문제인 만큼 BFS가 순회할 수 있는 방향은 위, 아래, 상, 하, 좌, 우로 총 6방향이다.

따라서 dx, dy뿐만 아니라 dh 배열을 추가했다.

 

leftTomato는 익지 않은 토마토의 개수다.

BFS가 모든 상자의 순회를 끝냈음에도 익지 않은 토마토가 있다면 -1을 반환하면 되고,

bfs 함수를 호출하기 전에 애초에 leftTomato가 0이라면 모든 토마토가 익었다는 의미이므로 0을 출력하면 된다.

 

bfs 함수는 이전 문제들에서 작성한 함수들과 크게 다르지 않다.

일단 익은 토마토의 개수가 여러 개일 수 있기 때문에 solution 함수 안에서 익은 토마토를 모두 큐에 넣는다.

그 후 bfs를 호출하면 큐에서 front를 하나씩 꺼내서 현재 위치에서 위, 아래, 상, 하, 좌, 우에 있는 토마토를 검사하고,

익지 않은 토마토에 대해서 d를 계산해서 큐에 넣은 후 익은 토마토로 바꾼다.

=> d는 토마토가 익는 데 걸리는 기간이기 때문에 큐에서 pop할 때마다 day에 업데이트한다.

 

큐가 비면 모든 과정이 끝난 것이고 leftTomato를 검사해서 결과를 반환한다.

leftTomato가 0이라면 모든 토마토가 잘 익은 것이므로 day를 반환하고,

0이 아니라면 익지 않은 토마토가 남은 것이기 때문에 -1을 반환한다.

 

 

 

지금은 큐를 연결리스트로 구현했지만, 처음 작성했을 땐 이전 문제들처럼 평범하게 배열을 사용해서 풀었다.

하지만 배열을 사용했더니 시간초과가 떴다.

시간복잡도를 줄이기 위해 삽입과 삭제가 O(1)이 될 수 있게 큐를 연결리스트로 구현하고 다시 제출했더니 해결할 수 있었다.