Rotting Oranges

오랜만에 풀어보는 문제이다. BFS 몰랐던 당시에 어떻게 단순 FOR 루프로만 풀어볼려고 했다가 망했던 문제. 너비탐색을 배우기에 정말 좋은 미디엄 문제라고 생각한다. DFS, BFS 문제들은 정해진 틀이 있고 거기서 얼마나 변형시키냐에 따라 문제 난이도가 달라진다고 생각한다. 그러나 Rotting Oranges 문제는 가장 교과서다운 BFS 문제이기에 배우기 좋다.

2D벡터안에서 0은 빈공간, 1은 신선한 오렌지, 2는 썩은 오렌지를 뜻한다
썩은 오렌지가 매 분마다 4가지 방향으로 신선한 오렌지를 썩힐수 있다할때
가장 최단시간으로 모든 오렌지를 썩히는 시간을 구하는거고 모든 오렌지가 썩혀질수 없다면 -1을 반환하면 된다.

정석으로 풀었다고 생각하고 여기서 중요시 여길점은 dir 벡터와 queue를 세팅하는 방법이다

그 외에 코드는 BFS를 위한 최적화 코딩이므로 다른 비슷한 유형의 문제를 봤을때 이 코드를 참고하여 문제를 해결하면 좋을거같다.

배운점:
1. queue<pair<int,int>>
2. vector<vector> dir
3. grid[x][y] 값 변형시키기