[LeetCode] 994. Rotting Oranges

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

Rotting Oranges - LeetCode

Rotting Oranges - Medium

 

 

grid에 오렌지들과 그 상태가 들어있다.

0일경우엔 없고, 1일 경우 신선한 오렌지, 2일 경우 썩은 오렌지가 있다.

썩은 오렌지는 1분이 지날때마다 위,아래,왼쪽,오른쪽 오렌지를 썩게 만든다.

이때, 모든 오렌지가 썩을때까지 걸리는 최소 시간을 구하는 문제다. 만약 모든 오렌지가 썩을 수 없다면 -1을 리턴한다.

 

구현만 하면 되는 아주 간단한 문제로 보이는데, 괜히 어이없는 삽질하다가 시간을 날렸다..

 

처음에 신선한 오렌지의 개수 f를 세어준다.

그 후, 큐를 하나 생성해주자. 

이 큐에는 썩은 오렌지들의 좌표가 들어간다.

 

이 큐에서 큐 사이즈만큼 뽑아내어 썩히는 과정을 진행한다.

새로 썩는 오렌지는 큐에 좌표를 다시 넣어주고, 이 오렌지의 상태는 0이나 -1로 바꿔주고 f--를 해준다.

그리고 시간을 ++ 해준다.

 

이 과정을 큐가 비어있거나 f=0이 될때까지 반복한다.

큐가 비었거나 f=0이 되었을때, f=0이라면 시간을, f가 0이아니라면 -1을 리턴해주자.

 

전체 풀이 코드

 

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int f=0,r=0;
        queue<pair<int, int>> q;
        for (int i=0; i<grid.size(); i++) for (int j=0; j<grid[0].size(); j++) {
            if (grid[i][j]==1) f++;
            if (grid[i][j]==2) q.push(make_pair(i,j));
        }
        while (!q.empty() && f) {
            int s = q.size();
            for (int i=0; i<s; i++) {
                pair<int, int> p = q.front();
                q.pop();
                if (p.first && grid[p.first-1][p.second]==1) q.push(make_pair(p.first-1, p.second)),grid[p.first-1][p.second]=0,f--;
                if (p.second && grid[p.first][p.second-1]==1) q.push(make_pair(p.first, p.second-1)),grid[p.first][p.second-1]=0,f--;
                if (p.first<grid.size()-1 && grid[p.first+1][p.second]==1) q.push(make_pair(p.first+1, p.second)),grid[p.first+1][p.second]=0,f--;
                if (p.second<grid[0].size()-1 && grid[p.first][p.second+1]==1) q.push(make_pair(p.first, p.second+1)),grid[p.first][p.second+1] = 0,f--;
            }
            r++;
        }
        return f==0?r:-1;
    }
};