[LeetCode] 994. Rotting Oranges, Medium

1. 문제

• 아래와 같은 정보로 2차원 배열이 주어질 때, 전체 오렌지가 상하는데 걸리는 최소 시간을 구하라.
  • 0: 빈 칸.
  • 1: 신선한 오렌지
  • 2: 썩은 오렌지
• 썩은 오렌지 4방향의 위치한 신선한 오렌지는 1분 후 썩는다.

2. 해결

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

function orangesRotting(grid: number[][]): number {
    const n = grid.length;
    const m = grid[0].length;

    let fresh = 0;
    const queue = [];
    const visited = Array.from({length: n}, () => Array(m).fill(false));

    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,0]);
                visited[i][j] = true;
            } else if(grid[i][j] === 1) fresh++;
        }
    }    

    let lastMinute = 0;
    while(queue.length) {
        const [x,y,minute] = queue.shift();
        lastMinute = minute;

        for(let i = 0; i < 4; i++) {
            const adjustX = dx[i] + x;
            const adjustY = dy[i] + y;

            if(adjustX >= 0 && adjustX <n && adjustY >=0 && adjustY < m && !visited[adjustX][adjustY] && grid[adjustX][adjustY] === 1) {
                visited[adjustX][adjustY] = true;
                fresh--;
                queue.push([adjustX, adjustY, minute + 1]);
            }
        }
    }

    return fresh === 0 ? lastMinute : -1;
};

• 썩은 오렌지가 1개 있다는 얘기가 없으므로, 여러 군데에서 동시에 시작해야 하기 때문에 처음 전체 탐색을 통해 썩은 오렌지 정보를 큐에 담는 거 까지 추측해냈다.
• 이후 BFS 탐색까지 잘 구현했지만, BFS 종료 조건과 결과 반환 시점에 에러가 있었다.
  • 종료 조건은, 처음 탐색할 때 신선한 오렌지 수를 세어놓고 썩을 때 마다 감소시켜 0인걸 확인하면 된다.
  • 반환 시점은 While문 중간에서 리턴하게 되면 전체 오렌지가 썩은 시점이 확실하지 않기 때문에 모든 BFS 탐색이 끝난 후, 마지막 시간을 반환해야 모든 오렌지가 썩는 데 걸린 시간 정보로써 의미가 생긴다.