[baekjoon] #7576 토마토 (Node.js)

📖 문제

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

☃️ 풀이

고민에 고민에 고민을 거듭한 문제. 계속해서 시간 초과가 발생하여 애를 좀 먹었다.

일단 bfs를 활용하는 문제라는 건 확실히 알고 있었고, 처음 생각한 알고리즘은 다음과 같다.

1. 토마토 밭을 초기화하고, 익은 토마토가 위치한 좌표를 ripe 배열에 넣는다.
   - 이 때, 하루가 지난 뒤 익게 될 토마토의 위치 배열 temp도 함께 생성한다.
2. while문을 돌리며 ripe 배열에서 좌표를 하나씩 꺼낸다.
3. 이 좌표의 상하좌우에 익지 않은 토마토가 있는지 확인한다.
   - 있다면 해당 격자의 값을 1로 갱신하고 ripe 배열에 좌표 정보를 넣는다.
   - 없다면 다음으로 넘어간다.
4. 덜 익은 토마토가 없거나, 더 이상 다음 위치로 이동할 수 없을 경우 반복문을 종료한다.
5. 토마토 밭에 덜 익은 토마토가 존재한다면 cnt를 -1로 바꾼다.
6. cnt를 출력한다.

처음에는 ripe 배열에서 좌표를 꺼내는 작업을 ripe.shift()로 처리했다. 근데 계속 시간 초과가 발생하여 알아보니 배열의 shift() 메서드는 시간 복잡도가 최악의 경우 O(n)이라고 한다. 그것도 모르고 여지껏 queue를 따로 구현할 필요가 없다고 좋아하고 있었다..

그래서 결국 Queue를 구현하기로 했다. 구현하는 것 자체는 크게 어렵지 않으니 생략하고, 큐를 사용하니 단번에 문제가 해결되었다.

그리고는 다른 사람들이 해결한 풀이법을 확인했는데, 웬걸 큐를 사용하지 않는 분들도 있었다. 이들은 아이템을 꺼내는 것이 아니라 추가만 하였고, 별도의 idx 변수를 선언하여 해당 인덱스 값을 늘려가며 배열에 접근했다. 그래서 O(1)의 시간 복잡도로 익은 토마토의 좌표에 접근할 수 있었다. 그리고 익은 토마토와 인접한 덜 익은 토마토가 더이상 존재하지 않는다면, 즉 ripe.length === idx가 된다면 반복문을 종료한다.

--
여담인데, 처음 생각한 알고리즘에서 shift() 대신 pop()을 사용하니 문제가 해결되긴 하더라.. 하루가 지난 뒤의 배열을 별도로 만들어줬기 때문에 흐름 상에도 문제가 없다.

오랜만에 큐 자료형에 대해 다시 정리하고 좋은 게 좋은거라 생각하자.

💽 소스코드

idx를 활용한 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [m, n] = input.shift().split(' ').map(Number);
let tomato = [];
let ripe = [];
let day = 0;

for (let i = 0; i < n; i++) {
  const t = input.shift().split(' ').map(Number);
  tomato.push(t);

  t.forEach((num, idx) => num === 1 && ripe.push([idx, i]));
}

const dxs = [0, 0, 1, -1];
const dys = [1, -1, 0, 0];

bfs();

tomato.forEach((arr) => {
  if (arr.includes(0)) day = -1;
});

console.log(day);

function bfs() {
  let idx = 0;
  
  while (ripe.length !== idx) {
    let [x, y] = ripe[idx];

    for (let d = 0; d < 4; d++) {
      const nx = x + dxs[d];
      const ny = y + dys[d];

      if (in_range(nx, ny) && !tomato[ny][nx]) {
        tomato[ny][nx] = tomato[y][x] + 1;
	    day = tomato[y][x];
        ripe.push([nx, ny]);
      }
    }
    
    idx++;
  }
}

function in_range(x, y) {
  return 0 <= x && x < m && 0 <= y && y < n;
}

Queue 자료형을 활용한 풀이

// Queue의 구현을 포함하면 너무 길어지기 때문에 생략하겠다.
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [m, n] = input.shift().split(' ').map(Number);
let tomato = [];
let ripe = new Queue();
let day = 0;

for (let i = 0; i < n; i++) {
  const t = input.shift().split(' ').map(Number);
  tomato.push(t);

  t.forEach((num, idx) => num === 1 && ripe.enqueue([idx, i]));
}

const dxs = [0, 0, 1, -1];
const dys = [1, -1, 0, 0];
let last = ripe.end();

bfs()

tomato.forEach((arr) => {
  if (arr.includes(0)) day = 0;
});

console.log(day - 1);

function bfs() {
  while (ripe.length > 0) {
    const [x, y] = ripe.dequeue();

    for (let d = 0; d < 4; d++) {
      const nx = x + dxs[d];
      const ny = y + dys[d];

      if (in_range(nx, ny) && !tomato[ny][nx]) {
        tomato[ny][nx] = tomato[y][x];
        ripe.enqueue([nx, ny]);
      }
    }

    if ([x, y].toString() === last.toString()) {
      day += 1;
      last = ripe.end();
    }
  }
}

function in_range(x, y) {
  return 0 <= x && x < m && 0 <= y && y < n;
}