Leetcode - 994. Rotting Oranges

문제

주어진 오렌지 상자에 썪은오렌지(2), 정상오렌지(1) 없음(0) 이 존재한다. 썪은 오렌지는 한번에 상하좌우 4방향을 오염시킨다. 몇 번만에 모든 오렌지가 썪는지 파악해라.

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

참고로 썪은 오렌지가 두개 이상일 수있음.

Input: grid = [[2,1,1],[1,1,2],[0,1,1]]
Output: 2

해결 BFS

처음에 재귀로 풀려고시도했지만 잘 안풀렸음. queue사용해 pop할때 상하좌우 위치를 체크해서 push하면됨. queue를 이용해 그래프의 bfs 순회 하는것과 구조상 동일

class Solution {
    int r_size;
    int c_size;
    bool is_fresh(vector<vector<int>>& grid, int r, int c) {
        if (r < 0 || r >= r_size || c < 0 || c >= c_size)
            return false;
        if (grid[r][c] == 1)
            return true;
        return false;
    }
    void rotting(queue<tuple<int, int, int>> &q, vector<vector<int>> &grid, int r, int c, int step) {
        if (is_fresh(grid, r, c)) {
            grid[r][c] = 2;
            q.push(make_tuple(r, c, step + 1));
        }
    }
public:
    int orangesRotting(vector<vector<int>>& grid) {
        r_size = grid.size();
        c_size = grid[0].size();
        queue<tuple<int, int, int>> q; // (row, col, step)
        int r = 0; 
        int c = 0;
        int step = 0;
        
        for (int i = 0; i < r_size; i++) {
            for (int j = 0; j < c_size; j++) {
                if (grid[i][j] == 2)
                    q.push(make_tuple(i, j, 0));
            }
        }
        
        while (!q.empty()) {
            tuple<int, int, int> check = q.front();
            q.pop();
            r = get<0>(check);
            c = get<1>(check);
            step = get<2>(check);
            
            rotting(q, grid, r+1, c, step);
            rotting(q, grid, r, c+1, step);
            rotting(q, grid, r-1, c, step);
            rotting(q, grid, r, c-1, step);
        }

        for (int i = 0; i < r_size; i++) {
            for (int j = 0; j < c_size; j++) {
                if (grid[i][j] == 1) {
                    step = -1;
                    break;
                }
            }
        }
        return step;
    }
};