7576. 토마토

백준 7576번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

7576번: 토마토

풀이

아이디어

이미 익어있는 토마토들이 인접한 주변의 익지 않은 토마토들을 익게 하면서 익은 토마토들의 범위를 넓혀가는 느낌이다… => BFS!

토마토들의 정보를 입력받으면서 익은 토마토들을 큐에 넣어주었다. 그리고 그 큐를 돌아가면서 사방으로 인접해있는 익지 않은 토마토들을 익히고, 새로 익은 토마토들은 큐에 넣어주고 이런 기본적인 BFS 를 따라서 토마토들을 익혀 주었다.

그리고 문제 조건에서 토마토가 모두 익지 못하는 상황을 걸러줘야 한다 했으므로 다른 토마토를 익힐 수 있는 토마토가 없는데 박스 상에는 덜익은 토마토가 있는 경우에는 더이상 덜익은 토마토들을 익힐 방법이 없으므로 -1을 출력해주었다.

코드

/*
2022-4-3
7576_토마토
https://www.acmicpc.net/problem/7576
*/

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

int n, m, day;
int box[1001][1001];

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

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

	queue<pair<int, int> > q;
	pair<int, int> tomato;
	int dx[] = {1, 0, -1, 0};
	int dy[] = {0, -1, 0, 1};
	cin >> m >> n;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> box[i][j];
			if (box[i][j] == 1)
				q.push(make_pair(i, j));
		}
	}
	day = 0;
	while (!check_tomato())
	{
		if (q.empty())
		{
			cout << -1;
			return (0);
		}
		int size = q.size();
		for(int k = 0; k < size; k++)
		{
			tomato = q.front();
			q.pop();
			for(int i = 0; i < 4; i++)
			{
				int nx = tomato.second + dx[i];
				int ny = tomato.first + dy[i];
				if (ny < 0 || ny >= n || nx < 0 || nx >= m)
					continue;
				if (box[ny][nx] == 0)
				{
					box[ny][nx] = 1;
					q.push(make_pair(ny, nx));
				}
			}
		}
		day++;
	}
	cout << day;

	return (0);
}