[백준 7576] 토마토

문제 링크 : https://www.acmicpc.net/problem/7576

7576번: 토마토

익은 토마토가 중심이 되어서 bfs탐색을 하는 문제이다

 

대충 그림으로 표현하자면 다음과 같다

검정색 테두리는 토마토들이 담긴 격자이고

 

빨간색 동그라미가 초기 익은 토마토이다

 

초기 익은 토마토에서부터 파란색 -> 초록색 순서대로 bfs탐색을 하면서

 

안익은 토마토가 범위 안에 들어오면 익게 하고 

 

모든 토마토가 익을때 까지 계속 탐색하면 된다.

---

물론 bfs는 진행할 수 있는 모든 격자에 진행했는데

 

안익은 토마토가 남아있을 수 있다 (아래와 같은 경우)

 

0 -1

-1 1

 

이를 위해서 bfs 탐색이 끝나고 (큐가 비어지고)

 

안익은 토마토가 있는지 확인해야된다

---

#include <iostream>
#include <queue>
#define n_ 1005
using namespace std;

int n, m;
int arr[n_][n_];
// 빠른 상하좌우 탐색을 위한 dx, dy배열
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

typedef struct Point {
	int x, y, cnt;
}point;

// 토마토 bfs에 사용될 큐, 정보단위는 point 구조체
queue <point> que;

// 매번 bfs가 진행되고 남아있는 안익은 토마토의 개수를 알려주는 함수
int check() {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) {	// 안익은 토마토가 0
				cnt++;
			}
		}
	}
	return cnt;
}

int bfs() {
	point now;

	// 현재 큐에는 초기 입력에 들어온 익은 토마토들이 들어있음
	// 따라서 추가로 push하고 진행할 필요 없이 바로 시작
	while (!que.empty()) {
		now = que.front();	// 맨 앞의 격자
		que.pop();

		for (int i = 0; i < 4; i++) {	
			// a,b는 새로운 x,y좌표
			int a = now.x + dx[i];
			int b = now.y + dy[i];

			// 격자를 벗어나면 탐색 안해도 됨
			if (a == -1 || a == n || b == -1 || b == m)continue;

			// 만약 안익은 토마토면
			if (arr[a][b] == 0) {
				arr[a][b] = 1;	//익게 하고
				que.push({ a, b, now.cnt + 1 });	// 그 토마토를 기준으로 bfs 탐색 추가
			}
		}
	}

	// res에는 모든 
	int res = check();
	if (res != 0) {	// 전부 탐색했는데도 안익은 토마토가 있으면
		// -1로 둘러 쌓여서 영원히 익을 수 없는 토마토인거임
		return -1;
	}
	else {	// 모든 토마토가 익었으면 마지막 bfs단계의 cnt가 전부 익는데 걸린 시간
		return now.cnt;
	}
}

int main(void) {
	cin >> m >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				que.push({ i,j ,0 });
			}
		}
	}

	cout << bfs() << endl;
}