백준 7576 토마토

문제

제한사항

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [n, m] = input.shift().split(" ").map(Number);
const arr = input.map((v) => v.split(" ").map((v) => +v));

const solution = (n, m, arr) => {
  const queue = [];
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  let index = 0
  let answer = 0;
  let zeroCount = 0;

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (arr[i][j] === 1) {
        queue.push({ x: i, y: j, count: 0 });
      } else if (arr[i][j] === 0) {
        zeroCount++;
      }
    }
  }
  while (index < queue.length) {
    const { x, y, count } = queue[index++];
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (arr?.[nx]?.[ny] === 0) {
        queue.push({ x: nx, y: ny, count: count + 1 });
        zeroCount--;
        arr[nx][ny] = 1;
        answer = Math.max(answer, count + 1);
      }
    }
  }
  return zeroCount ? -1 : answer;
};

console.log(solution(n, m, arr));

• bfs의 변형 문제이다.
• 처음에 토마토가 들어있는 좌표를 큐에 넣어주고 bfs를 시작한다.
• zeroCount 변수를 이용해 0의 개수를 세어준다.
• queue.shift()를 사용하면 되지만 수행시간 이슈가 생겨서 index변수를 이용했다.