[LeetCode] 994. Rotting Oranges 문제 풀이

https://leetcode.com/problems/rotting-oranges/

Rotting Oranges - LeetCode

 

문제 내용

썩은 귤이 있는데 4방향으로 인접해 있는 곳으로 퍼진다.

몇일 만에 남은 귤이 다 썩는지 출력하고 다 안썩으면 -1 출력하는 문제

 

귤이 썩는 과정

 

문제 풀이

썩은 귤을 모두 Queue에 담고 하나씩 퍼져가면서 day를 구하면 된다.

그리고 마지막에 귤을 검사해서 멀쩡한 귤이 있으면 -1을 출력하면 된다.

 

class Solution {
public:
    int dy[4] = {-1,0,1,0};
    int dx[4] = {0,1,0,-1};
    
    int orangesRotting(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        
        queue<tuple<int,int,int>> q;
        for (int y = 0; y < row; ++y) {
            for (int x = 0; x < col; ++x) {
                if (grid[y][x] == 2)
                    q.push(make_tuple(y, x, 0));
            }
        }
        
        int days = 0;
        
        while(!q.empty()) {
            auto [y, x, day] = q.front();
            q.pop();
            
            days = day;

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

                if (ny < 0 || ny == row || nx < 0 || nx == col)
                    continue;
                if (grid[ny][nx] != 1)
                    continue;

                grid[ny][nx] = 2;
                q.push(make_tuple(ny, nx, day+1));
            }
        }
        
        for (int y = 0; y < row; ++y) {
            for (int x = 0; x < col; ++x) {
                if (grid[y][x] == 1) {
                    return -1;
                }
            }
        }
        return days;
    }
};