각 셀마다 상한 오렌지, 신선한 오렌지, 빈 칸이 주어진다. 매 분이 지날 때마다 상한 오렌지에서 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;
};