백준 토마토

이 문제의 포인트는 토마토가 동시 다발적으로 퍼져 나간다는것이다. 즉 처음부터 토마토가 있는 지점들을 저장해놓고 시작해야하는게 핵심이다.

 

맵을 입력 받을 때 토마토 지점을 큐에 넣고 빈큐가 될 때 까지 돌린다.

 

초기에 현재 토마토 값 + 1을 해줘서 그 지점이 몇일째 토마토가 된건지 표시 해주는것이다. 그리고 더 이상 퍼져나갈 토마토가 없으면 종료. 

 

그리고 맵을 돌며 안익은 토마토가 있다면 -1을 출력해주고 그외 최대값을 갱신해주자.

 

그리고 최대값에서 -1을 해주면 몇일이 걸렸는지 확인 가능

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

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

int main() {

	int n, m;
	cin >> m >> n;

	queue<pair<int, int>> q;

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

	int ans = 0;

	while (!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int nx = cx + dx[d];
			int ny = cy + dy[d];

			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (maps[nx][ny] == 0) {
					maps[nx][ny] = maps[cx][cy] + 1;
					q.push({ nx, ny });
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (maps[i][j] == 0) {
				cout << -1 << endl;
				return 0;
			}
			if (ans < maps[i][j])
				ans = maps[i][j];
		}
	}

	cout << ans - 1 << endl;

}