994 Rotting Oranges https://leetcode.com/problems/rotting-oranges/

Medium

You are given an m x n grid where each cell can have one of three values:

•

0 representing an empty cell,

•

1 representing a fresh orange, or

•

2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Plain Text
복사

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Plain Text
복사

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Plain Text
복사

Constraints:

•

m == grid.length

•

n == grid[i].length

•

1 <= m, n <= 10

•

grid[i][j] is 0, 1, or 2.

My solution

셀에 새 오렌지가 없을 때까지 경과해야 하는 최소 시간(분)을 반환합니다.* 이것이 불가능하면 '-1'을 반환

for (let i = 0; i <= M; i++) {
    for (let j = 0; j <= N; j++) {
      if (grid[i][j] === 2) {
        queue.push([i, j]);

        while (queue.length) {
          const x = queue.shift();
          let flag = false;

          for (let pos = 0; pos < 4; pos++) {
            const nx = x[0] + dx[pos];
            const ny = x[1] + dy[pos];

            if (nx >= 0 && ny >= 0 && nx <= M && ny <= N && grid[nx][ny] === 1) {
              grid[nx][ny] = 2;
JavaScript
복사

방문한 1을 썩게 했으므로 2로 바꾸어준다. 하지만 2로 바꾸어주면 queue의 기존에 2였던 것과 2로 바뀐 것의 좌표를 구별할 수 없다. 미리 queue에 기존 2의 좌표들을 넣고 반복문을 시행한다.

for문은 queue.length만큼만 돌아야 되는데 내부에서 queue.shift()로 인해서 queue.length가 변화하기 때문에 미리 queue.length가 변경되어 제대로 동작하지 않는다.

while (queue.length) {
    const size = queue.length; // 여기서의 queue.length를 유지한다.
    console.log(size, queue.length);

    for (let k = 0; k < size; k++) {
JavaScript
복사

소스코드

/**
 * @param {number[][]} grid
 * @return {number}
 */
const orangesRotting = function (grid) {
  const M = grid.length;
  const N = grid[0].length;
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  const queue = [];
  let answer = 0;

  for (let i = 0; i < M; i++) {
    for (let j = 0; j < N; j++) {
      if (grid[i][j] === 2) queue.push([i, j]);
    }
  }

  while (queue.length) {
    const size = queue.length;

    for (let k = 0; k < size; k++) {
      const x = queue.shift();

      for (let i = 0; i < 4; i++) {
        const nx = x[0] + dx[i];
        const ny = x[1] + dy[i];

        if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
          if (grid[nx][ny] === 1) {
            grid[nx][ny] = 2;
            queue.push([nx, ny]);
          }
        }
      }
    }

    if (queue.length) answer++;
  }

  if (grid.flat().includes(1)) return -1;
  return answer;
};

// test('TC1', () => {
//   expect(
//     orangesRotting([
//       [2, 1, 1],
//       [1, 1, 0],
//       [0, 1, 1],
//     ])
//   ).toStrictEqual(4);
// });
// test('TC2', () => {
//   expect(
//     orangesRotting([
//       [2, 1, 1],
//       [0, 1, 1],
//       [1, 0, 1],
//     ])
//   ).toStrictEqual(-1);
// });
// test('TC3', () => {
//   expect(orangesRotting([[0, 2]])).toStrictEqual(0);
// });
test('TC4', () => {
  expect(
    orangesRotting([
      [2, 1, 1],
      [1, 1, 1],
      [0, 1, 2],
    ])
  ).toStrictEqual(2);
});
// test('TC5', () => {
//   expect(orangesRotting([[0, 2, 2]])).toStrictEqual(0);
// });
JavaScript
복사