[leetcode] 994. Rotting Oranges

 

문제

 

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<Orange> queue = new LinkedList<>();
        int xLength = grid.length;
        int yLength = grid[0].length;
        int time = -1;
        int count = 0;
        for(int i = 0; i < xLength; i++) {
            for(int j = 0; j < yLength; j++) {
                if (grid[i][j] == 2) {
                    queue.add(new Orange(i, j));
                }
                if (grid[i][j] == 1) {
                    count += 1;
                }
            }
        }
        Queue<Orange> temp = new LinkedList<>();
        int rotten = 0;
        while(true) {
            temp = new LinkedList<>(); 
            time += 1;

            while(!queue.isEmpty()) {
                Orange orange = queue.poll();

                int x = orange.x;
                int y = orange.y;
                if (x - 1 >= 0 && grid[x - 1][y] == 1) {
                    grid[x - 1][y] = 2;
                    temp.add(new Orange(x - 1, y));
                    rotten += 1;
                }
                if (x + 1 < xLength && grid[x + 1][y] == 1) {
                    grid[x + 1][y] = 2;
                    temp.add(new Orange(x + 1, y));
                    rotten += 1;
                }
                if (y - 1 >= 0 && grid[x][y - 1] == 1) {
                    grid[x][y - 1] = 2;
                    temp.add(new Orange(x, y - 1));
                    rotten += 1;
                }
                if (y + 1 < yLength && grid[x][y + 1] == 1) {
                    grid[x][y + 1] = 2;
                    temp.add(new Orange(x, y + 1));
                    rotten += 1;
                }
            }

            if (temp.isEmpty()) {
                break;
            }
            queue = temp;
        }

        if (rotten != count) {
            return -1;
        }
        return time;

    }

    class Orange {
        public int x;
        public int y;
        public Orange(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            return "x: " + x + ", y: " + y;
        }
    }
}