전략

토마토는 익으면 하루하루 한칸씩 전염되어 익는다.

처음에 입력 받은 것을 한번 훑어서, 익은것의 좌표를 큐에 넣어둔다. (익어있던 것들이 다음날부터 주변 익힘) 이때 일자를 체크해야 하므로 좌표와 함께 일자 넣는것 고려 앞으로 익힐 토마토 개수 체크해둔다.

처음에 익힐 토마토 0이면 0출력 바로 하고 종료 큐가 비었는데 익힐 토마토 남았으면 -1출력 큐 종료 되고 익힐 토미토도 0이면 일자를 출력(밖에서 트레킹 해야할것 같다)

풀이1 - 시간초과

바로 BFS로 풀었으나 큐로 배열을 사용해서 시간초과가 났습니다.

const [cr, ...lines] = `${require('fs').readFileSync('dev/stdin')}`
  .trim()
  .split('\n');

const [col, row] = cr.split(' ').map(Number);
const box = lines.map((line) => line.split(' ').map(Number));
const WESN = [
  [0, -1],
  [-1, 0],
  [0, 1],
  [1, 0],
];
const q = [];
let unripe = 0;

// 토마토박스 전격분석.
for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    const cur = box[i][j];
    if (cur === 1) {
      q.push([i, j, 0]);
      continue;
    }
    if (cur === 0) {
      unripe++;
    }
  }
}

// 익은게 하나도 없으면 못익힘
if (!q.length) console.log(-1);
// 안익은게 없음
if (!unripe) {
  console.log(0);
} else {
  // 안익은게 있으니 익히자
  while (q.length) {
    const [r, c, d] = q.shift();
    for (let i = 0; i < 4; i++) {
      const [toX, toY] = WESN[i];
      const x = r + toX;
      const y = c + toY;
      if (x < 0 || y < 0 || x === row || y === col) continue;
      if (box[x][y] === 0) {
        box[x][y] = 1;
        q.push([x, y, d + 1]);
        unripe--;
      }
    }
    if (!q.length) {
      console.log(unripe ? -1 : d);
    }
  }
}

풀이2

큐를 구현해서 기존 배열을 대체하니 정답처리 되었습니다.

const [cr, ...lines] = `6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1`
  .trim()
  .split('\n');

const [col, row] = cr.split(' ').map(Number);
const box = lines.map((line) => line.split(' ').map(Number));
const WESN = [
  [0, -1],
  [-1, 0],
  [0, 1],
  [1, 0],
];

class Queue {
  constructor() {
    this.storage = new Map();
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.storage.size;
  }

  add(item) {
    if (!this.storage.size) {
      this.storage.set(0, item);
    } else {
      this.storage.set(++this.rear, item);
    }
  }

  pop() {
    const item = this.storage.get(this.front);
    if (item == null) return null;
    if (this.storage.size === 1) {
      this.storage.clear();
      this.front = this.rear = 0;
    } else {
      this.storage.delete(this.front++);
    }
    return item;
  }
}

const q = new Queue();
let unripe = 0;

for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    const cur = box[i][j];
    if (cur === 1) {
      q.add([i, j, 0]);
      continue;
    }
    if (cur === 0) {
      unripe++;
    }
  }
}

if (!q.size()) console.log(-1);
if (!unripe) {
  console.log(0);
} else {
  while (q.size()) {
    const [r, c, d] = q.pop();
    for (let i = 0; i < 4; i++) {
      const [toX, toY] = WESN[i];
      const x = r + toX;
      const y = c + toY;
      if (x >= 0 && y >= 0 && x < row && y < col && box[x][y] === 0) {
        box[x][y] = 1;
        q.add([x, y, d + 1]);
        unripe--;
      }
    }
    if (!q.size()) {
      console.log(unripe ? -1 : d);
    }
  }
}

풀고나서

배열로 큐를 사용하는 경우 조금만 입력이 큰 경우에도 쉽게 시간초과가 날 수 있으니 큐를 제대로 구현해서 사용해야겠다는 생각을 하게 되었습니다!