(Leet Code JS)Rotting Oranges

https://leetcode.com/problems/rotting-oranges/

Rotting Oranges - LeetCode

BFS 활용.

 

m x n 크기의 grid를 BFS 전에 한번 훑어준다.

grid를 순회하면서 멀쩡한 오렌지(grid[i][j] === 1)가 있으면 orange++을 한다.

그렇지 않고 썩은 오렌지(grid[i][j] === 2)가 있다면 queue에 해당 좌표를 넣어준다.

 

한번 순회가 끝나고, orange가 0이라면 바로 0을 리턴한다.

 

그렇지 않으면 queue를 비우면서 주변 오렌지를 썩힌다.

4방향으로 좌표를 탐색하며, 탐색할 좌표가 배열의 범위를 벗어나지 않고 해당 좌표의 숫자가 1이라면 queue에 넣어주고, 2로 바꾼다.

또한, 멀쩡한 오렌지가 썩었기 때문에 orange--를 한다.

 

모든 탐색이 끝나고 orange가 남아있다면, 모든 오렌지를 썩힐 수 없기 때문에 -1을 리턴.

그렇지 않고 멀쩡한 오렌지가 없다면 answer - 1을 리턴한다.

answer - 1을 하는 이유는 처음 시작할 때는 카운팅을 하지 않기 때문이다.

const orangesRotting = (grid) => {
    let answer = 0;
    let orange = 0;
    const m = grid.length;
    const n = grid[0].length;
    const queue = [];
    const direct = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(grid[i][j] === 1){
                orange++;
            } else if(grid[i][j] === 2){
                queue.push([i, j]);
            }
        }
    }
    
    if(!orange){
        return 0;
    }
    
    while(queue.length){
        let length = queue.length;
        
        while(length--){
            const [x, y] = queue.shift();
            
            for(let i = 0; i < 4; i++){
                const nx = x + direct[i][0];
                const ny = y + direct[i][1];

                if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 1){
                    orange--;
                    grid[nx][ny] = 2;
                    queue.push([nx, ny]);
                }
            }
        }
        answer++;
    }
    
    return orange > 0 ? -1 : answer - 1;
};