[Graph - BFS, Medium] Rotting Oranges

https://leetcode.com/problems/rotting-oranges/description/?envType=study-plan-v2&envId=leetcode-75

이 문제는 BFS로 풀 때, 첫 큐에 들어갈 원소가 여러개다.
썩은 오렌지가 여러 곳에 있을 수 있기 때문

따라서 썩은 오렌지 순회용 2중 for문을 돌며 큐에 넣는다.

이후에는 역시 상하좌우 순회하면 되는데, 신선한 오렌지가 있는 쪽까지 체크해주면 되겠다.
신선한 오렌지인지 여부를 체크하면 되니 visited 배열은 따로 필요 없다.

왜냐면 큐를 통해 BFS 순회한다는 것 자체가 해당 오렌지도 썩는다는 뜻이니 2로 바꿔줄 것이기 때문. 이후에는 신선하지 않기 때문에 이쪽으로 접근 안함

나는 마지막에 또 2중 포문을 돌려 신선한 오렌지가 하나라도 있으면 -1을 리턴하도록 했다.
하지만 최적화를 한다면 처음 썩은 오렌지를 셀 때 신선한 오렌지 수도 카운트하고, BFS 순회시마다 신선한 오렌지 카운트를 감소시켜 주고 마지막에 신선 == 썩은인지 체크해도 된다.

어차피 O(M∗N)시간복잡도라서 어떻게 해도 큰 상관은 없고, 직관적이기 때문에 그냥 냅두겠다.

class Solution {
    private int[] dx = {1, -1, 0, 0};
    private int[] dy = {0, 0, -1, 1};
    public int orangesRotting(int[][] grid) {
        
        int m = grid.length;
        int n = grid[0].length;

        Queue<int[]> queue = new LinkedList<>();

        // find and offer to queue rotten oranges
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[] {i, j, 0});
                }
            }
        }

        int max = 0;
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0], y = current[1], minutes = current[2];

            for (int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    queue.offer(new int[] {nx, ny, minutes + 1});
                    max = Math.max(max, minutes + 1);
                }
            }
        }

        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }

        return max;
    }
}