토마토 C++ - 백준 7576

https://www.acmicpc.net/problem/7576

이 문제는 bfs로 풀어야겠다는 생각이 들었다.

이 문제의 포인트는 날짜 계산이었다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int M;
int N;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int days=0;
int ripecnt;
int notomatos=0;
int tomatocnt=0;
int ftomatos;

int graph[1001][10001];
queue<pair<int, int>> q;

void bfs(){
	ripecnt=q.size();
	ftomatos=ripecnt;
	while(!q.empty()){
		if(ripecnt==0){
			ripecnt=q.size();
			days++;
		}
		int x=q.front().first;
		int y=q.front().second;
		
		q.pop();
		
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			if(0<=nx && nx<N && 0<=ny && ny<M){
				if(graph[nx][ny]==0){
					graph[nx][ny]=1;
					q.push(make_pair(nx,ny));
					tomatocnt++;					
				}
			}
		}
		ripecnt--;
	}
}

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	cin >> M >> N;
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			cin >> graph[i][j];
			if(graph[i][j]==1){
				q.push(make_pair(i,j));
			}
			if(graph[i][j]==-1){
				notomatos++;
			}
		}
	}
	bfs();
	if(N*M-notomatos==tomatocnt+ftomatos){
		cout << days;
	}
	else{
		cout << -1;
	}
}

날짜 계산은
먼저, day0에서 익은 것들을 큐에 넣고
큐의 사이즈를 담는 변수를 선언했다.

bfs가 진행될 때 마다 변수의 값을 하나씩 줄이면서
이 값이 0이 되면 날짜를 하나씩 늘렸다.

그리고 마지막으로 토마토의 개수가 토마토가 없는 부분을 제외하고 난 후의 개수와 맞는지 체크하여 답을 출력했다.