[알고리즘] 토마토(7576)

구현 방식

• 원래는 익은 토마토마다 BFS 를 했는데, 그랬더니 중반 즈음에서 시간 초과가 발생했다.
• 맨처음 큐에 익은 토마토 위치를 모두 추가하면, BFS를 한번만 실행해도 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>

using namespace std;

void solution(int N, int M);
void bfs(int N, int M);

int graph[1001][1001];
queue<pair<int, int>> q;

int main()
{
	int N, M;
	cin >> M >> N;
	int empties = 0;

	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
		{
			int status;
			cin >> status;
			switch (status)
			{
			case(0):
				graph[y][x] = INT_MAX;
				break;
			case(1):
				graph[y][x] = 0;
				q.push({ y, x });
				break;
			case(-1):
				graph[y][x] = -1;
				empties++;
				break;
			}
		}

	int unRipenTomatoes = N * M - q.size() - empties;
	if (unRipenTomatoes == 0)
	{
		cout << 0 << endl;
		return 0;
	}
	solution(N, M);
}


void solution(int N, int M)
{

	bfs(N, M);


	int result = INT_MIN;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
		{
			if (graph[y][x] == INT_MAX)
			{
				cout << -1;
				return;
			}
			result = max(graph[y][x], result);

		}

	cout << result;
}

void bfs(int N, int M)
{
	pair<int, int> surround[4] = { {-1, 0},{1,0},{0,-1},{0,1} };

	while (!q.empty())
	{
		pair<int,int> currPos = q.front();
		q.pop();
		for (auto& surr : surround)
		{
			pair<int, int> nextPos = { currPos.first + surr.first ,currPos.second + surr.second };
			if (nextPos.first < 0 || N <= nextPos.first)
				continue;
			if (nextPos.second < 0 || M <= nextPos.second)
				continue;
			if (graph[nextPos.first][nextPos.second] == -1)
				continue;
			if (graph[nextPos.first][nextPos.second] == INT_MAX)
			{
				graph[nextPos.first][nextPos.second] = graph[currPos.first][currPos.second] + 1;
				q.push(nextPos);
			}
		}

	}

}