7576.토마토

이번 문제는 토마토이다! 비교적 쉬운 문제에 속한다.

BFS를 이용하면 간단히 풀 수 있는데 BFS로 퍼지면서(토마토가 익으면서) 내부의 값(걸리는 시간값)을 잘 지정해주어야한다!

7576번: 토마토

 

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <queue>

#define MAX 1001


using namespace std;

int n, m;

int map[MAX][MAX];

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

queue <pair<int, int>> tomato; //tomato 좌표


void search(){ // BFS
	int day = 0;
	while (!tomato.empty()){
		int x = tomato.front().first; //x좌표
		int y = tomato.front().second;//y좌표
		tomato.pop(); //좌표다뺐으니 제거
		for (int i = 0; i < 4; i++){ //상하좌우 탐색
			int ax = x + dx[i]; 
			int ay = y + dy[i];
			if (ax < 0 || ay < 0 || ax >= n || ay >= m)
				continue; // map 범위 벗어나면 넘어감
			if (map[ax][ay] == 0){ // 토마토가 안익었으면
				map[ax][ay] = map[x][y] + 1; //익혀준다(값 중요)
				tomato.push(make_pair(ax, ay));//토마토좌표 저장
			}
		}
	}
	int answer = 0; //정답
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			answer = max(answer, map[i][j]); //익는 날짜중 가장 높은값
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (map[i][j] == 0){ // 안익은 토마토가 있다면
				answer = 0; // 값음 0 이다.
				break;
			}
		}
	}
	cout << answer - 1 << "\n"; // 날짜 첫날은 빼야하니까 -1 을 해줘야한다.
}
int main() {
	//freopen("7576.txt", "r", stdin);
	cin >> m >> n;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cin >> map[i][j];
			if (map[i][j] == 1)
				tomato.push(make_pair(i, j));
		}
	}
	search();
	return 0;
}