[Leetcode] 994. Rotting Oranges - BFS

1. 문제링크

Rotting Oranges - LeetCode

 

 

2. key point - queue를 사용하자

1) 상한 오렌지 q에 넣기

2) 오렌지는 자기 주변 4셀(상하좌우)만 썩게 할 수 있음

3) 상태가 1에서 2로 변경되는 오렌지는 q에 넣어주기

4) q가 empty가 될 때 까지 반복한다

 

 

3. solution

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int days = 0;
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        vector<pair<int, int >> dir = {{-1,0}, {0, -1}, {1, 0}, {0, 1}};
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 2){
                    q.push({i, j});
                }
            }
        }

        while(!q.empty()){
            int size = q.size();
            bool rotted = false;
            while(size-- > 0){
                pair<int, int> node = q.front();            
                q.pop();
                for(int t = 0; t < dir.size(); t++){
                    int row = node.first + dir[t].first;
                    int col = node.second + dir[t].second;
                    if((row >= 0 && row < m && col >= 0 && col < n) && grid[row][col] == 1){
                        grid[row][col] = 2;
                        q.push({row, col});
                        rotted = true;
                    }
                }                
            }
            if(rotted)
                days++;
        }

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