[C++] 백준 7576 - 토마토

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

7576번: 토마토

---

풀이

• bfs를 실행하게 되면 배열을 해당 모습으로 값이 변한다.

익은 토마토를 큐에 집어넣고 탐색했을 때의 배열 상태

• 1(익은 토마토)가 담겨있는 곳을 큐에 담는다.
• 주변에 0(익지 않은 토마토)이 존재할 때  하루 지났다는 의미로 해당 위치에 1을 증가시킨 값을 집어넣는다.
• 배열에 있는 최대값을 저장하여 1을 빼준 값이 토마토가 모두 익은 날이 된다.

코드

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAX 1001
#define _X first
#define _Y second

int board[MAX][MAX];

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

int M, N;	// 가로, 세로
int maxDay = 0;
int day = 0;

queue<pair<int, int>> q;

void Bfs()
{
	while (!q.empty())
	{
		pair<int, int> cur = q.front();
		int x = cur._X;
		int y = cur._Y;

		q.pop();

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

			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;	// 범위를 벗어났다면
			if (board[nx][ny] == -1) continue;						// 토마토가 없다면

			// 익지 않은 토마토가 있을 경우, 
			if (board[nx][ny] == 0)
			{
				board[nx][ny] = board[x][y] + 1;
				q.push({ nx, ny });
			}
		}
	}
}

// 익지 않은 토마토가 있는지 확인하고 모두 익었으면 일수 출력
void CheckBoard()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			// 익지 않은 토마토가 있을 때는 -1 출력 후 for문 탈출
			if (board[i][j] == 0)
			{
				cout << -1;
				return;
			}
			// 배열의 값을 저장하는 day 변수가 최대 일수보다 크다면 바꿔준다.
			day = board[i][j];
			if (maxDay < day)
				maxDay = day;
		}
	}
	// 익은 토마토가 1이기 때문에 일수를 구하기 위해서는 1을 빼줘야 한다.
	cout << maxDay - 1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	// 가로, 세로 입력
	cin >> M >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			// 배열 입력
			cin >> board[i][j];
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (board[i][j] == 1)
			{
				// 익은 토마토가 있으면 큐에 넣음
				q.push({ i, j });
			}
		}
	}

	Bfs();
	CheckBoard();

	return 0;
}