[leetcode #994 Rotting Oranges]

Problem

You are given an m x n grid where each cell can have one of three values:

・ 0 representing an empty cell,
・ 1 representing a fresh orange, or
・ 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

・ m == grid.length
・ n == grid[i].length
・ 1 <= m, n <= 10
・ grid[i][j] is 0, 1, or 2.

Idea

이 문제의 전제는 썩은 오렌지가 옆에 있을 경우 신선한 오렌지가 1분 뒤에 썩은 오렌지가 된다는 것이다. Grid 위에 있는 오렌지 전부가 썩은 오렌지가 되기까지 최소 몇 분이 걸리는 지 구하면 된다.

매번 Grid 전체를 탐색하는 방법도 있겠지만 그렇게 풀면 Time Limit Exceeded가 뜰 것 같아 리스트를 이용하기로 했다. 처음에 Grid 전체를 탐색하면서 썩은 오렌지의 경우 리스트에 넣어주고, 신선한 오렌지의 경우는 오렌지 갯수를 센다. 신선한 오렌지의 갯수를 세는 이유는 썩은 오렌지가 될 수 있는 가능성을 전부 적용하고 나서도 신선한 오렌지가 남는지 확인하기 위함이다.

시간을 측정하기 위해 썩은 오렌지가 되고 나서 경계값을 리스트에 넣어줬다. 만약 리스트의 원소가 경계값이고 남은 원소가 없는 경우 더 이상 썩은 오렌지가 생길 가능성이 없는 것이다. 리스트에 원소가 남아있는 경우 금방 썩은 오렌지가 있다는 뜻이므로, 시간을 1분 늘리고 썩은 오렌지가 생기는 경우를 더 확인한다.

리스트에서 꺼낸 썩은 오렌지의 인덱스를 이용해 주변에 있는 신선한 오렌지를 썩은 오렌지로 바꾼다. 바뀐 썩은 오렌지는 리스트에 더해지고, 신선한 오렌지의 갯수는 1씩 감소시킨다. 이렇게 하면 경계값 혼자 남을 때까지 전체 Grid를 다 확인할 수 있다.

신선한 오렌지가 남아있을 경우에만 -1을 리턴하고, 그렇지 않을 경우 걸린 시간을 리턴하면 된다.

Solution

class Solution {
    public int orangesRotting(int[][] grid) {
        int rowLen = grid.length;
        int colLen = grid[0].length;

        List<int[]> list = new ArrayList<>();
        int cnt = 0;
        for (int i=0; i < rowLen; i++) {
            for (int j=0; j < colLen; j++) {
                if (grid[i][j] == 1)
                    cnt++;
                else if (grid[i][j] == 2)
                    list.add(new int[]{i, j});
            }
        }

        list.add(new int[]{-1, -1});

        int minMinutes = 0;
        while (!list.isEmpty()) {
            int[] rotten = list.remove(0);
            int rottenRow = rotten[0];
            int rottenCol = rotten[1];
            if (rottenRow == -1 && rottenCol == -1) {
                if (list.size() == 0)
                    break;
                list.add(new int[]{-1, -1});
                minMinutes++;
                continue;
            }

            if (rottenRow != 0 && grid[rottenRow-1][rottenCol] == 1) {
                grid[rottenRow-1][rottenCol] = 2;
                list.add(new int[]{rottenRow-1, rottenCol});
                cnt--;
            }
            if (rottenRow != rowLen-1 && grid[rottenRow+1][rottenCol] == 1) {
                grid[rottenRow+1][rottenCol] = 2;
                list.add(new int[]{rottenRow+1, rottenCol});
                cnt--;
            }
            if (rottenCol != 0 && grid[rottenRow][rottenCol-1] == 1) {
                grid[rottenRow][rottenCol-1] = 2;
                list.add(new int[]{rottenRow, rottenCol-1});
                cnt--;
            }
            if (rottenCol != colLen-1 && grid[rottenRow][rottenCol+1] == 1) {
                grid[rottenRow][rottenCol+1] = 2;
                list.add(new int[]{rottenRow, rottenCol+1});
                cnt--;
            }
        }

        return cnt != 0 ? -1 : minMinutes;
    }
}

아주 훌륭한 결과가 나왔다!

Reference

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