[C++ / 백준 7576번] 토마토

문제

 

 

시행 착오

 

두 개 이상의 토마토가 0일차에 들어 있을 때, 두 번 이상의 bfs 를 한 번에 하는 방법을 잠깐 고민했었다.

 

해결 방법

 

bfs 를 시작하기 전에 배열을 순회해 0일차 토마토의 좌표를 큐에 넣어놓고 bfs 를 시작했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

using namespace std;

/*
* 익은 토마토의 영향을 받아야 익는다.
* 토마토가 없는 칸도 있을 수 있다.
* 
*/

int tomato[1000][1000];
int arr[1000][1000];
bool visited[1000][1000];

int M, N;
int cnt = 0;

queue<pair<int, int>> q;
queue<pair<int, int>> q2;

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

int findMax()
{
	int maxNum = -1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			maxNum = max(maxNum, arr[i][j]);
		}

	}
	return maxNum;
}
bool check()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (tomato[i][j] != -1 && tomato[i][j] == 0)
			{
				return false;
			}
		}

	}
	return true;
}

void bfs(int y, int x)
{

	if (x == -1 && y == -1)
	{
		while (!q2.empty())
		{
			visited[q2.front().first][q2.front().second] = true;
			q.push(make_pair(q2.front().first, q2.front().second));
			q2.pop();
		}
	}
	else
	{
		visited[y][x] = true;
		q.push(make_pair(y,x));
	}



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

		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (!visited[ny][nx]
				&& tomato[ny][nx] == 0
					&& (ny >= 0 && ny < N)
					&& (nx >= 0 && nx < M))
			{
				q.push(make_pair(ny, nx));

				tomato[ny][nx] = 1;
				arr[ny][nx] = arr[y][x] + 1;
				visited[ny][nx] = true;

			}
		}

	}


}



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


	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> tomato[i][j];
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (tomato[i][j] == 1)
			{
				q2.push(make_pair(i, j));
			}
		}
	}

	bfs(-1, -1);


	if (!check())
	{
		cout << -1;
	}
	else
		cout << (cnt = findMax());


	return 0;
}