Leet code (Medium) : 994. Rotting Oranges (BFS) - JAVA

 

 

BFS의 대표적인 문제유형 중 하나인, 감염 문제이다.

메모리 효율을 위해 visited 객체를 따로 생성해서 쓰지않고 방문한 곳은 주어진 그래프에서 값을 업데이트 하는 방식으로 했다.

 

이미 썩은 오렌지가 몇개 있는 상태에서 시작하므로 큐를 첨에 시간 초깃값을 -1로 설정해서 큐를 돌게 한다.

 

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

        int fresh = 0;

        Queue<int[]> queue = new LinkedList<>();
        for(int row = 0; row < rows; row++){
            for(int col = 0; col < cols; col++){
                if(grid[row][col] == 1) {
                    fresh++;
                } else if(grid[row][col] == 2){
                    queue.offer(new int[]{row, col});
                }
            }
        }

        // 애초에 신선한 오렌지가 없을때 0
        if(fresh == 0) return 0;
        // 애초에 썩은 오렌지가 없을때 -1
        if(queue.isEmpty()) return -1;

        int[] dr = {-1,0,0,1};
        int[] dc = {0,-1,1,0};

        int minutes = -1;

        // queue가 비워질때까지 반복
        while(!queue.isEmpty()){
            // while을 한번돌 때 같은 level(같은 거리)의 오렌지들을 다 돈다.
            // 따라서 거리를 ++해줘야함.
            minutes++;

            // 현재 큐에 담긴 동일 거리의 오렌지들에 대해서 다 처리해야하므로
            // 현재 큐 사이즈만큼의 for문이 하나더 필요.
            int n = queue.size();
            for(int i = 0; i < n; i++){
                int[] orange = queue.poll();

                // 4방향의 모든 지점에 대해 처리
                for(int j = 0; j < 4; j++){
                    int row = orange[0] + dr[j];
                    int col = orange[1] + dc[j];

                    if(row < 0|| row >= rows || col < 0 || col >= cols) continue;
                    if(grid[row][col] == 0 || grid[row][col] == 2) continue;
                    
                    queue.offer(new int[]{row, col});
                    grid[row][col] = 2;
                    fresh--;
                }
            }
        }
        
        // 모든 오렌지가 변했다면 ~
        if(fresh == 0) return minutes;

        return -1;
    }
}