[BOJ] 7576 토마토 C++

개요

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

7576번: 토마토

골드급 BFS문제다.

풀이

토마토가 모두 익는 최소 일 수를 출력해야 하기 때문에 BFS를 사용해야 한다.

토마토를 입력받은 후 큐에 입력 받은 익은 토마토를 전부 넣어주었다.

이렇게 하면 익은 토마토들에서 동시에 점점 퍼져나가서 다른 토마토를 익게 할 것이다.

상하좌우로 탐색하기 때문에 OutOfBounds가 나지 않게 조심해야 한다.

또한 처음이 아닌데(firstSize 변수로 체크) 이미 들렀거나(1) 빈 박스(-1) 일 경우 넘어가 주어야 한다.

탐색이 끝난 후 배열을 확인해봤을 때 안 익은 토마토(0)가 있을 경우 -1을 출력해 준다.

아닐 경우 걸린 일 수(ans)를 출력한다.

코드

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
constexpr int LIMIT = 1002;

struct Box
{
	int y;
	int x;
	int cnt;
};
int M, N;
int tmt[LIMIT][LIMIT];
int dy[] = { 0,0,-1,1 };
int dx[] = { -1,1,0,0 };
int ans;

void BFS()
{
	queue<Box> q;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (tmt[i][j] == 1) q.push({ i, j, 0 });
		}
	}
	int firstSize = q.size();

	while (!q.empty())
	{
		int qy = q.front().y;
		int qx = q.front().x;
		int qc = q.front().cnt;
		q.pop();

		if (qy < 1 || qy > N || qx < 1 || qx > M) continue;
		if (tmt[qy][qx] && firstSize-- < 1) continue;
		tmt[qy][qx] = 1;

		ans = qc++;
		for (int i = 0; i < 4; i++)
		{
			int y = qy + dy[i];
			int x = qx + dx[i];
			q.push({ y,x,qc });
		}
	}
}

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

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

	BFS();

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (!tmt[i][j]) ans = -1;
		}
	}
	cout << ans;
}