994. Rotting Oranges 쉬운설명 BFS 사용

994. Rotting Oranges

 

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

 

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.

 

Example 3: 

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

 

 

계획

문제 설명

 

우선 인풋으로 오랜지의 상태를 나타내는 grid array를 받습니다. 2는 썩은 오렌디를 나타내고, 1은 노말 오랜지 0은 그위치에 오랜지가 없음을 나타냅니다. 

그리고 위와 같이 1분마다, 썩은 오랜지의 상하좌우로 붙어있는 오랜지도 썩게됩니다. 

 

그리고 만약 하나만 고립되어  썩지 않을수있다면 -1을 리턴합니다. 

 

구현 전략

 

우선 상하좌우위치를 알아야합니다. 그리고 주변에 있다면,  1 -> 2로 바꾸고, 다음 루프로 이동한다. 그리고 다음루프로 이동할때마다 minute을 증가시킨다. 

 

해설

var orangesRotting = function(grid) {
  const height = grid.length;
  const width = grid[0].length;
  let fresh = 0;
  const queue = [];
  for (let i = 0; i < height; i++) {
    for (let j = 0; j < width; j++) {
      if (grid[i][j] === 2) queue.push([i, j]);
      if (grid[i][j] === 1) fresh++;
    }
  }
  let minute = 0;
  while (queue.length) { //queue길이만큼 반복 
      
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const [x, y] = queue.shift();
      if (x - 1 >= 0 && grid[x - 1][y] === 1) {
        grid[x - 1][y] = 2; //2썩은것다고 나타낸다.
        fresh--; //fresh의 갯수를 줄입니다. 
        queue.push([x - 1, y]); // 새롭게 썩은 애를 추가한다. 
      }
      if (x + 1 < height && grid[x + 1][y] === 1) {
        grid[x + 1][y] = 2;
        fresh--;
        queue.push([x + 1, y]);
      }
      if (y - 1 >= 0 && grid[x][y - 1] === 1) {
        grid[x][y - 1] = 2;
        fresh--;
        queue.push([x, y - 1]);
      }
      if (y + 1 < width && grid[x][y + 1] === 1) {
        grid[x][y + 1] = 2;
        fresh--;
        queue.push([x, y + 1]);
      }
    }
    if (queue.length > 0) minute++;
  }
  return fresh === 0 ? minute : -1;// 만약 fresh갯수가 0이면 minute을 리턴 아니면 안썩은 오랜지가 있다는뜻이기때문에 -1 리턴
};