994. Rotting Oranges

994. Rotting Oranges

문제

각 셀마다 상한 오렌지, 신선한 오렌지, 빈 칸이 주어진다. 매 분이 지날 때마다 상한 오렌지에서 4방향으로 인접한 신선한 오렌지가 감염된다고 가정할 때 인접한 모든 오렌지가 상할 때 걸리는 시간(분)을 구하는 문제이다.

테스트 케이스

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

재귀적 호출을 하는 DFS와 달리 큐(queue) 자료구조를 사용하는 것이 일반적이다. 현재 큐에 담긴 (상한 오렌지)를 모두 검사하는 것이 포인트이다. BFS는 동시에 범위를 넓히며 탐색할 수 있기 때문에 주어진 시작점에서 몇회 만에 끝단까지 도달하는지를 구하는 문제라고 볼 수 있다.

풀이

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  // 상,하,좌,우 배열 
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; 
  let queue = [];
  let minutes = 0;

  // 감염된 오렌지를 큐에 담는다. 
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 2) {
        queue.push([i, j]);
      }
    }
  }

  // 감염된 오렌지 주변의 셀을 탐색해 (BFS)
  // 신선한 오렌지가 있으면 감염시키고 큐에 담고 체크(infected)한다. 
  // 큐에 감염된 오렌지가 있으면 계속 반복. 
  while (queue.length > 0) {
    let size = queue.length;
    let infected = false;
    // 현재 큐에 담긴 오렌지만큼 반복한다. 
    for (let i = 0; i < size; i++) {
      const [currI, currJ] = queue.shift();
      // 꺼낸 오렌지의 4방향을 탐색한다. 
      for (let direction of directions) {
        const nextI = currI + direction[0];
        const nextJ = currJ + direction[1];
        // 만약 다음 셀이 범위 안에 있고 신선하다면,
        if (nextI >= 0 && nextI < rows && nextJ >= 0 && nextJ < cols && grid[nextI][nextJ] === 1) {
          // 감염을 하나라도 시키면 체크(infected)한다. 
          // 그리고 방금 감염된 오렌지 셀을 큐에 담는다. (다음 탐색을 위해)
          grid[nextI][nextJ] = 2;
          infected = true;
          queue.push([nextI, nextJ]);
        }
      }
    }

    // 감염시킨 오렌지가 있으면 minute를 +1한다. 
    if (infected) {
      minutes++;
    }
  }

  // 탐색 후에 신선한 오렌지가 남아있으면 -1을 반환한다.
  // 인접할 수 없는 곳에 있으므로
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 1) {
        return -1;
      }
    }
  }

  return minutes;
};