[백준] 알고리즘 7576번 - 토마토 문제

#include <bits/stdc++.h>
using namespace std;
int m, n,cnt=0;
int check[1001][1001];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };

queue<pair<int,int>> qu;
void bfs() {
	while (!qu.empty()) {
		int x = qu.front().first;
		int y = qu.front().second; 
		qu.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx<0 || nx>=n || ny<0 || ny>=m) continue;
			if (check[nx][ny] == 0) {
				 
				check[nx][ny] = check[x][y]+1;
				qu.push(make_pair(nx, ny));
				 
			}
		}
	}
}
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   cin >> m >> n;
   for (int i = 0; i < n; i++) {
	   for (int j = 0; j < m; j++) {
		   cin >> check[i][j];
		   if (check[i][j] == 1) {
			   qu.push(make_pair(i, j));
		   }
	   }
   }
   bfs();
   for (int i = 0; i < n; i++) {
	   for (int j = 0; j < m; j++) {
		   if (check[i][j] == 0) {
			   cout << -1;
			   return 0;
		   }
		   if (cnt < check[i][j]) cnt = check[i][j];
	   }
   }
   cout << cnt-1;
}

이 문제는 BFS를 이용하여 해결 할 수 있다.

문제에 최소 일수 등 이런 힌트가 있으면 BFS로 먼저 접근해서 생각해보는게 좋습니다.

상 하 좌 우 좌표를 저장하는 DX,DY 배열을 이용하여 각 지점마다 토마토가 없으면 그 이전 토마토에 의해 토마토가 익게되고 만약 CHECK에 0이 하나라도 있으면 문제에서 토마토가 무조건 다 익어야한다고 하였으니, -1을 출력하게 해준다.