백준 7576 토마토

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 익은 토마토가 있을경우 하루뒤 그토마토의 좌우상하의 토마토가 익는 방식으로 하여 모든 토마토가 익는데 까지 걸리는 날을 계산하는 문제입니다. 하루마다 익은 토마토 기준으로 좌우상하의 토마토가 익게되므로 이 문제는 bfs 방식으로 해결을 하였습니다.

 

저는 우선 토마토 배열에다 토마토 정보를 입력받고 처음 익은 토마토들을 큐에 넣었습니다. 그리고 그토마토들을 하나씩 bfs를 진행하여 주며 처음 0일날 큐의 사이즈를 미리 len 변수에 저장해놓고 0일날 토마토들이 모두 빠져나오면 +1일을 더해주었습니다. 그리고 나서 +1일날의 큐의 사이즈를 또다시 len 변수에 집어넣고 그토마토들에 대하여 bfs를 하는 방식으로 총 날짜를 계산하였습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <queue>

using namespace std;

int tomato[1002][1002];
int nextx[4] = {1,0,-1,0}; //좌우를 표시하기 위한 배열 
int nexty[4] = {0,1,0,-1}; //상하를 표시하기 위한 배열 

queue<pair<int ,int>> q;
int M,N;
int daynum;
int num;

void bfs() {
		
	int len = q.size();
	while(!q.empty()) { // n일째 되는 날짜의 모든 토마토가 주변 토마토를 익히게 되는경우 
		if(len == num) {
			daynum++;
			len = q.size(); 
			num = 0;
		}
		
		for(int i = 0; i < 4; i++) {
				
			if(q.front().first+nextx[i] < 0 || q.front().first+nextx[i] >= N || q.front().second+nexty[i] < 0 || q.front().second+nexty[i] >= M ) //범위 검사 
				continue;
					
			if(tomato[q.front().first+nextx[i]][q.front().second+nexty[i]] == 0) { //토마토가 안익었다면 익힘 
				q.push(make_pair(q.front().first+nextx[i], q.front().second+nexty[i]));
				tomato[q.front().first+nextx[i]][q.front().second+nexty[i]] = 1;
			}
		}
		q.pop();
		num++;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> M >> N;
	bool flag = true;
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++) 
			cin >> tomato[i][j];
			

	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++ ) 
			if(tomato[i][j] == 1) {
				q.push(make_pair(i, j));
			}
		
	
	bfs();
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++ )
			if(tomato[i][j] == 0) { //만일 익지 않은 토마토가 있다면 -1 출력 
				cout<<-1;
				return 0;
			}
			
	cout << daynum;
	
	return 0;
}