[백준] 7576_토마토

[문제]: 7576번: 토마토 (acmicpc.net)

 

익은 토마토는 여러 곳에 동시에 있을 수 있다. 기억해야 할 것은 시작점이 여러 개인 BFS는 그냥 모든 시작점을 큐에 넣고 BFS 돌리면 끝이다. 방문 되었는지의 여부를 나타내는 배열이 아닌 거리(몇일 걸렸는지 나타내는 시간)를 의미하는 days배열임을 주의 할 것. 깊이가 1 증가할 때마다 days도 1씩 증가한다.

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int board[1002][1002];
int days[1002][1002];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int M, N;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	queue<pair<int, int>> q;
	cin >> M >> N;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> board[i][j];
			if (board[i][j] == 1)
				q.push({ i, j });
			if (board[i][j] == 0)// 익지않은 토마토인 경우
				days[i][j] = -1;
		}
	}

	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (days[nx][ny] >= 0 || board[nx][ny] == -1) continue;
			days[nx][ny] = days[cur.first][cur.second] + 1;
			q.push({ nx, ny });
		}
	}
	
	int ret = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (days[i][j] == -1) {
				cout << -1;
				return 0;
			}
			ret = max(ret, days[i][j]);
		}
	}
	cout << ret << '\n';
	return 0;
}