[리트코드] 994. Rotting Oranges - js (BFS)

1. 문제

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

Rotting Oranges - LeetCode

2. 코드

처음 작성한 코드)

예상했지만..타임아웃

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function(grid) {
    if(check(grid)) return 0;
    let time = 0;

    while(!check(grid)){
        for(let i=0;i<grid.length;i++){
            for(let j=0;j<grid[i].length;j++){
                if(grid[i][j]===1){
                    if((i > 0 && grid[i-1][j]===2) || (i<grid.length-1 && grid[i+1][j]===2)
                    || (j<grid[i].length-1 && grid[i][j+1]===2) || (j>0 && grid[i][j-1]===2)){
                        grid[i][j] = 2;
                    }
                }
            }
        }
        time++;
    }

    return time;
};

const check = (grid) => {
    const flatGrid = [];

    for(let i=0;i<grid.length;i++){
        flatGrid.push(...grid[i]);
    }

    return (!flatGrid.includes(1)) ? true : false;
}

정답)

처음엔 싱싱한 오렌지를 썩은 오렌지로 바꾸는 것에만 포커스를 맞췄다. 그러다 보니 while 문 안에 이중 for 문을 넣고, while 문 종료 조건에 영향을 미치는 함수 내부에서도 for문을 넣어 당연한 타임아웃을 만들게 되었다.

정답을 보니 싱싱한 오렌지에 포커스를 맞추는게 아니라 이미 썩은 오렌지들이 다른 오렌지들을 같이 썩게 만드는 것에 포커스를 맞추어야 한다. 그래서 큐(BFS)를 사용한다.

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
    const queue = [];
    let noFreshOranges = 0;
    let time = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === 2) queue.push([i, j]); // 썩은 오렌지
            if (grid[i][j] === 1) noFreshOranges++; // 싱싱한 오렌지 총 합
        }
    }
    
    // 썩은 오렌지가 좌우양옆을 탐색하며 싱싱한 오렌지를 찾아 변환시킨다.
    while (queue.length) {
        const n = queue.length;

        let freshOrngCount = 0; // 싱싱한 오렌지 중 썩은 오렌지가 된 오렌지의 총 합
        for (let i = 0; i < n; i++) {
            const [x, y] = queue.shift();
            // right
            if ((y < grid[x].length - 1) && (grid[x][y + 1] === 1)) {
                freshOrngCount++;
                grid[x][y + 1] = 2
                queue.push([x, y + 1]);
            }
            // bottom
            if ((x < grid.length - 1) && (grid[x + 1][y] === 1)) {
                freshOrngCount++;
                grid[x + 1][y] = 2
                queue.push([x + 1, y]);
            }
            // top
            if ((x >= 1) && (grid[x - 1][y] === 1)) {
                freshOrngCount++;
                grid[x - 1][y] = 2
                queue.push([x - 1, y]);
            }
            // left
            if ((y >= 1) && (grid[x][y - 1] === 1)) {
                freshOrngCount++;
                grid[x][y - 1] = 2
                queue.push([x, y - 1]);
            }
        }
        if (freshOrngCount) time++; // 싱싱한 오렌지에서 썩은 오렌지로 변한 오렌지가 하나라도 있다면
        noFreshOranges -= freshOrngCount; // 싱싱한 오렌지 총합 - 변한 오렌지 총합
    }

    return !noFreshOranges ? time : -1;
};