leetcode link

Description

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.

994. 썩어가는 오렌지

당신은 m x n 크기의 grid가 주어지는데, 각 셀은 다음 세 가지 값 중 하나를 가질 수 있습니다:

• 0은 빈 셀을 나타냅니다.
• 1은 신선한 오렌지를 나타냅니다.
• 2는 썩은 오렌지를 나타냅니다.

매 분마다, 썩은 오렌지와 4방향으로 인접한 신선한 오렌지는 썩게 됩니다.

신선한 오렌지가 없게 될 때까지 경과해야 하는 최소 분수를 반환하세요. 만약 이것이 불가능하다면 -1을 반환하세요.

예제 1:

입력: grid = [[2,1,1],[1,1,0],[0,1,1]]
출력: 4

예제 2:

입력: grid = [[2,1,1],[0,1,1],[1,0,1]]
출력: -1
설명: 왼쪽 하단 모서리의 오렌지 (행 2, 열 0)는 4방향으로만 썩기 때문에 절대 썩지 않습니다.

예제 3:

입력: grid = [[0,2]]
출력: 0
설명: 0분에 이미 신선한 오렌지가 없기 때문에 답은 0입니다.

제약 조건:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j]는 0, 1, 또는 2입니다.

Solution

class Solution {
    final int[][] directions = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } }; // 4방향 이동

    public int orangesRotting(int[][] grid) {
        int minute = 0;

        int m = grid.length;
        int n = grid[0].length;
        int freshOrangeCount = 0;
        Queue<int[]> queue = new LinkedList<>();

        // 신선한 오렌지 수를 세고, 썩은 오렌지의 위치를 큐에 추가
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (grid[row][col] == 1)
                    freshOrangeCount++;
                else if (grid[row][col] == 2)
                    queue.offer(new int[] { row, col });
            }
        }

        // 큐를 사용한 BFS로 썩은 오렌지로부터 인접한 신선한 오렌지를 썩게 함
        while (!queue.isEmpty() && freshOrangeCount > 0) {

            // 각 분은 큐의 사이즈로 구분
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] position = queue.poll();

                for (int[] direction : directions) {
                    int newRow = position[0] + direction[0];
                    int newCol = position[1] + direction[1];

                    // 인접한 신선한 오렌지를 찾아 썩게 하고 큐에 추가
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
                        grid[newRow][newCol] = 2;
                        freshOrangeCount--;
                        queue.offer(new int[] { newRow, newCol });
                    }
                }
            }
            minute++;
        }

        return freshOrangeCount == 0 ? minute : -1;
    }
}