LeetCode 994 - Rotting Oranges (Medium)

 

💡 문제

LeetCode - 994번

 

🎯 풀이 과정

매 단위시간(minute) 마다 썩은 오렌지에 인접한 4방향에 위치한 오렌지가 함께 썩는다고 할때

주어진 grid 에서 모든 오렌지가 썩기까지 걸리는 시간을 구하는 문제입니다.

 

일반적인 BFS 탐색에서 약간의 변형이 필요한 유형입니다.

썩은 오렌지를 queue 에 넣어주고 queue 가 비어질때까지 반복해야지

각각의 단위 시간마다 현재 queue 에 담겨있는 오렌지들에 대해 BFS 를 할 수 있습니다.

 

보통 BFS 를 할 때 중복 방문을 피하기 위해 visit 같은 자료구조를 만들어 이용하는데,

여기서는 오렌지가 썩은 상태일 때를 이미 방문한 위치로 판단이 가능하므로

방문여부를 위한 별도의 자료구조는 만들어주지 않고 상태값으로 판단하도록 할 수 있습니다.

 

👨‍💻 코드

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function(grid) {
    const [ROW, COL] = [grid.length, grid[0].length]
    const dr = [1, -1, 0, 0]
    const dc = [0, 0, 1, -1]
    const queue = []

    function preparation() {
        for (let row = 0; row < ROW; row += 1) {
            for (let col = 0; col < COL; col += 1) {
                const isRotten = grid[row][col] === 2
                if (isRotten) {
                    queue.push([row, col])
                }
            }
        }
    }

    function outOfRange(row, col) {
        return row < 0 || row >= ROW || col < 0 || col >= COL
    }

    function rottening() {
        let minute = -1

        while (queue.length > 0) {
            let iterate = queue.length

            while (iterate > 0) {
                const [hr, hc] = queue.shift()

                for (let dir = 0; dir < 4; dir += 1) {
                    const [nr, nc] = [dr[dir] + hr, dc[dir] + hc]
                    if (outOfRange(nr, nc)) {
                        continue
                    }

                    const isEmpty = grid[nr][nc] === 0
                    const isRotten = grid[nr][nc] === 2

                    if (isEmpty || isRotten) {
                        continue
                    }

                    grid[nr][nc] = 2 // now, adjacent orange is rottening
                    queue.push([nr, nc])
                }

                iterate -= 1
            }

            minute += 1
        }

        return minute
    }  

    preparation()
    const minute = rottening()

    for (let row = 0; row < ROW; row += 1) {
        for (let col = 0; col < COL; col += 1) {
            const isFresh = grid[row][col] === 1
            if (isFresh) {
                return -1
            }
        }
    }

    return Math.max(minute, 0)
};