[백준 7576 - Node.js] 토마토

문제 링크

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

7576번: 토마토

풀이

const [MN, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [M, N] = MN.split(' ').map(v => +v);
const tomatoes = input.map(v => v.split(' ').map(v => +v));

class Node {
  constructor(x, y, count = -1) {
    this.x = x;
    this.y = y;
    this.count = count;
    this.next = null;
  }
}

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

  push(node) {
    if (!this.head) {
      this.head = node;
    }
    if (this.tail) {
      this.tail.next = node;
    }
    this.tail = node;
    this.size++;
  }

  shift() {
    if (!this.size) {
      return null;
    }
    const node = this.head;
    this.head = this.head.next;
    this.size--;
    return node;
  }
}

const queue = new Queue();
const offsetX = [0, 0, -1, 1];
const offsetY = [-1, 1, 0, 0];

let output = 0;
let zeroCount = 0;

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (tomatoes[i][j] === 1) {
      queue.push(new Node(j, i, 0));
    } else if (tomatoes[i][j] === 0) {
      zeroCount++;
    }
  }
}

while (queue.size) {
  const { x, y, count } = queue.shift();
  for (let i = 0; i < 4; i++) {
    const nx = x + offsetX[i];
    const ny = y + offsetY[i];
    if (tomatoes?.[ny]?.[nx] === 0) {
      queue.push(new Node(nx, ny, count + 1));
      zeroCount--;
      tomatoes[ny][nx] = 1;
      output = Math.max(output, count + 1);
    }
  }
}

console.log(zeroCount ? -1 : output);

각 토마토의 위치에서부터 상하좌우로 한 칸씩 안 익은 토마토를 익게 해야 한다.

익은 토마토에서 시작해서 더 이상 상하좌우에 안 익은 토마토가 없을 때까지 너비 우선 탐색을 하면 된다.

맨 처음 시작할 때 큐에 모든 익은 토마토를 넣고 너비 우선 탐색을 하면 모든 익은 토마토에서 동일한 속도로 다른 토마토들을 익히게 된다.

 

큐에 토마토를 넣을 때 현재 날짜를 포함한 데이터를 추가하여 시작 일자로부터 몇 일이 지나서 현재 토마토까지 도달했는지를 기록한다. 그리고 큐에 토마토를 넣을 때마다 이 날짜의 최대값을 갱신한다. (output)

최종적으로 너비 우선 탐색이 끝난 후 아직 익지 않은 토마토가 존재하면 -1을, 존재하지 않으면 output을 출력한다.

 

그런데 이 문제는 너비 우선 탐색을 할 때 큐에서 노드를 제거할 때, 배열의 shift 연산을 사용하게 되면 시간 초과가 난다. 따라서 shift를 사용하지 않는 방향으로 코드를 짜야 통과할 수 있다.

 

위 코드에서는 Queue를 직접 구현하여 해결하였다.

이 외에도 배열에 push만 하고 shift는 하지 않으면서 오로지 인덱스만 갖고 너비 우선 탐색을 구현할 수도 있다.

 

const [MN, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [M, N] = MN.split(' ').map(v => +v);
const tomatoes = input.map(v => v.split(' ').map(v => +v));
const queue = [];
const offsetX = [0, 0, -1, 1];
const offsetY = [-1, 1, 0, 0];

let output = 0;
let pointer = 0;
let zeroCount = 0;

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (tomatoes[i][j] === 1) {
      queue.push({ x: j, y: i, count: 0 });
    } else if (tomatoes[i][j] === 0) {
      zeroCount++;
    }
  }
}

while (pointer < queue.length) {
  const { x, y, count } = queue[pointer++];
  for (let i = 0; i < 4; i++) {
    const nx = x + offsetX[i];
    const ny = y + offsetY[i];
    if (tomatoes?.[ny]?.[nx] === 0) {
      queue.push({ x: nx, y: ny, count: count + 1 });
      zeroCount--;
      tomatoes[ny][nx] = 1;
      output = Math.max(output, count + 1);
    }
  }
}

console.log(zeroCount ? -1 : output);

그러나 Queue를 직접 구현한 풀이가 메모리와 속도에서 모두 더 나은 결과가 나왔다.