[백준/BOJ] 백준 7576번 : 토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

처음에 익어있는 토마토부터 왼쪽, 오른쪽, 위쪽, 아래쪽으로 bfs를 진행하며 익지 않은 토마토를 익은 토마토로 바꾼다. 이때 day는 가장 깊은 깊이이다.

 

코드

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

int box[1000][1000];
int dx_dy[4][2] = { {0,-1}, {0,1}, {-1,0}, {1,0} };
int m, n;

//박스에 익지 않은 토마토가 있는지 확인한다
bool checkBox()
{
	bool ret = true;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (box[i][j] == 0)
				return false;
		}

	return ret;
}

//익어있는 토마토들의 위치를 입력받고 bfs를 통해 다른 토마토가 모두 익을때 까지의 최소 날짜를 출력한다
int solve(vector<pair<int, int>> growed)
{
	int day = 0;
	vector<vector<bool>> discovered(n, vector<bool>(m, false));
	vector<vector<int>> depth(n, vector<int>(m));
	queue<pair<int, int>> q;

	//익어있는 토마토들의 위치를 시작으로 왼쪽, 오른쪽, 위쪽, 아래쪽 방향으로 bfs를 시작한다
	for (int i = 0; i < growed.size(); i++)
	{
		//익어있는 토마토들의 발견 표시를 한다
		discovered[growed[i].first][growed[i].second] = true;

		//bfs의 시작이므로 깊이를 0으로 한다
		depth[growed[i].first][growed[i].second] = 0;

		//큐에 익어있는 토마토들의 위치를 넣는다
		q.push(growed[i]);
	}

	//큐에 무언가 있다면 탐색을 진행한다
	while (!q.empty())
	{
		pair<int,int> here = q.front();
		q.pop();

		//탐색하는 위치는 익은 토마토가 된다
		box[here.first][here.second] = 1;

		//왼쪽, 오른쪽, 위쪽, 아래쪽 방향으로 탐색을 진행한다
		//단 탐색은 탐색을 진행할 위치가 box의 범위를 벗어나지 않아야 하고, 해당 위치에 익지 않은 토마토가 있어야 하고, 해당위치가 아직 발견되지 않았어야 한다
		for (int i = 0; i < 4; i++)
		{
			if (here.first + dx_dy[i][0] < n && here.first + dx_dy[i][0] >= 0 && here.second + dx_dy[i][1] < m && here.second + dx_dy[i][1] >= 0 && box[here.first + dx_dy[i][0]][here.second + dx_dy[i][1]] == 0 && discovered[here.first + dx_dy[i][0]][here.second + dx_dy[i][1]] == false)
			{
				//해당위치를 발견했다고 표시
				discovered[here.first + dx_dy[i][0]][here.second + dx_dy[i][1]] = true;

				//해당 위치의 깊이는 here의 깊이 + 1이다
				depth[here.first + dx_dy[i][0]][here.second + dx_dy[i][1]] = depth[here.first][here.second] + 1;

				//day는 가장 깊은 깊이이다(계속 업데이트 한다)
				day = max(day, depth[here.first + dx_dy[i][0]][here.second + dx_dy[i][1]]);

				//나중에 탐색할 위치 이므로 큐에 넣는다
				q.push(make_pair(here.first + dx_dy[i][0], here.second +dx_dy[i][1]));
			}
		}
	}

	//박스에 익지 않은 토마토가 있을때
	if (checkBox() == false)
		return -1;

	return day;
}

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

	int temp;
	vector<pair<int, int>> growed;

	cin >> m >> n;

	for(int i=0; i<n; i++)
		for (int j = 0; j < m; j++)
		{
			cin >> temp;
			box[i][j] = temp;

			//익은 토마토의 위치일때
			if (temp == 1)
				growed.push_back(make_pair(i, j));
		}

	cout << solve(growed);

	return 0;
}