백준 7576 : 토마토 ★

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

1. 접근

• 주변에!! 있는 토마토가 함께 익게 되므로 BFS가 적합하다고 생각했다.
• BFS의 내부에 상하좌우에 접근하는 코드를 작성한다. (배열값에 넣어도 됨)
• BFS를 탐색하면서, 해당 토마토를 익게 만든 토마토의 graph값에 1을 더하여 저장한다.
• 탐색이 끝나고 graph값 중 가장 큰 값 -1 을 한 값이 정답이 된다.
• BFS 탐색이 끝나고, 익지 않은 (0) 값이 존재하면 -1을 출력한다.
• graph 배열에 맨처음 입력값을 받으면서, 익은 토마토(1)의 좌표값을 바로 queue에 넣어준다.
  아래 예시의 경우, (4,6)에 있는 1 토마토가 퍼져야하는데, 기존의 BFS처럼 더 작은 인덱스값부터 BFS를 실행하게되면 (4,6)을 실행할 때에는 이미 모두 방문처리가 되어 실행할 수 없게 된다.

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

출력 : 6

2. 나의 풀이

#include <iostream>
#include <queue>
#define MAX 1001
using namespace std;

int graph[MAX][MAX];
int cnt=0;
int n, m;
queue<pair<int, int>> q;

void bfs() {
	while (!q.empty()) {
		int x,y;
		x = q.front().first;
		y = q.front().second;
		q.pop();

		if (x > 0) {
			if (graph[x - 1][y] ==0) {
				q.push(make_pair(x - 1, y));
				graph[x - 1][y] = graph[x][y] + 1; //영향을 준 토마토의 값 +1
			}
		}
		if (x < m - 1) {
			if (graph[x+1][y] == 0) {
				q.push(make_pair(x + 1, y));
				graph[x + 1][y] = graph[x][y] + 1;
			}
		}
		if (y > 0) {
			if (graph[x][y - 1] == 0) {
				q.push(make_pair(x, y - 1));
				graph[x][y - 1] = graph[x][y] + 1;
			}
		}
		if (y < n - 1) {
			if (graph[x][y+1] == 0) {
				q.push(make_pair(x, y + 1));
				graph[x][y + 1] = graph[x][y] + 1;
			}
		}
	}


}

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

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j];
			if (graph[i][j] == 1) q.push(make_pair(i, j)); //입력받으면서 바로 넣어줌
		}
	}

	bfs();

	int max = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (graph[i][j]==0) { //익지 않은 토마토가 있다면
				cout << "-1\n";
				return 0;
			}
			if (max < graph[i][j])
				max = graph[i][j]; //최댓값 저장
		}
	}

	cout << max-1 << "\n"; //맨처음 익은 토마토 값이 1이었으므로 빼줌


	return 0;
}