7576번: 토마토

• 접근 방법

가로, 세로의 크기가 각각 1000 이므로 익은 토마토 주위로 토마토를 익힌 다음에 모든 격자의 토마토를 계산하기에는 시간이 너무 많이 소요됩니다. 따라서 이미 익은 토마토들의 좌표의 정보를 큐에 저장해 놓고 BFS를 통해 익힌 다음에 (현재 일 + 1) 만큼을 익혀진 토마토들의 좌표에 저장해 놓음으로써 최소 일수를 구할 수 있다고 생각했습니다.

#include <iostream>
#include <vector>
#include <queue>

int N, M, exception_value1, exception_value2, num_tomato;
std::vector<std::vector<int> >tomato;
std::queue<std::pair<int, int> >q;
std::vector<std::vector<int> >visited;
std::vector<std::pair<int, int> > dir;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> M >> N;
	tomato.resize(N, std::vector<int>(M, 0));
	exception_value1 = 0;
	num_tomato = 0;
	visited.resize(N, std::vector<int>(M, 0));
	dir = {{0, 1} , {1, 0}, {-1, 0}, {0, -1}};
	for (size_t i = 0 ; i < N ; i++)
		for (size_t j = 0 ; j < M ; j++)
		{
			std::cin >> tomato[i][j];
			if (tomato[i][j] == 1)
			{
				q.push({i, j});
				exception_value1 ++;
			}
			if (tomato[i][j] != -1)
				num_tomato++;
		}
}

int exception_check()
{
	if (exception_value1 == num_tomato)
		return (-1);
	return (0);
}

void print_val(int n)
{
	if (n == -1)
		std::cout << 0;
	else if (n == -2)
		std::cout << -1;
	else
		std::cout << n;
}

void solve()
{
	int retrn_val;
	int date = 0;
	int x, y;
	int q_x, q_y;
	int max_date = -1;
	std::pair<int, int> a;

	if ((retrn_val = exception_check()))
	{
		print_val(retrn_val);
		return;
	}

	while (!q.empty())
	{
		a = q.front();
		q.pop();
		y = a.first;
		x = a.second;
		date = visited[y][x];
		for (size_t i = 0 ; i < 4 ; i++)
		{
			q_y = y + dir[i].first;
			q_x = x + dir[i].second;
			if (q_x < 0 || q_x >= M || q_y < 0 || q_y >= N || visited[q_y][q_x] || tomato[q_y][q_x] != 0)
				continue;
			visited[q_y][q_x] = date + 1;
			if (max_date < visited[q_y][q_x])
				max_date = visited[q_y][q_x];
			tomato[q_y][q_x] = 1;
			q.push({q_y , q_x});
		}
	}

	exception_value2 = 0;
	for (size_t i = 0; i < N ; i++)
	{
		for (size_t j = 0 ; j < M ; j++)
		{
			if (tomato[i][j] == 1)
				exception_value2++;
		}
	}
	if (exception_value2 != num_tomato)
		max_date = -2;
	print_val(max_date);
}

int main()
{
	input();
	solve();
	return (0);
}