[백준7576] 토마토 (C++)

점점 BFS에 익숙해져 가는 것 같다! 최대한 다른 소스코드 참고 안하고싶어서 계속 혼자 코딩했는데 결국 풀어내서 기쁘다🥰

📌 문제

BOJ 바로가기

전체 토마토를 익히는 데 어느 정도의 시간이 걸리는지 구해내야 한다. 그동안의 BFS문제는 시작점이 하나였는데, 이번 문제는 시작점이 여러군데일 수 있다는 점에서 이전 문제들과 차이가 있었다.

🗡 풀이

📍 큐에 처음에 push할 때 익은 토마토가 있는 위치를 전부 push해 주고 BFS를 돌려야 한다. 나는 처음에 이중 for문을 돌려서 익은 토마토가 있을 때마다 BFS를 돌리는 식으로 풀었는데, 이렇게 풀면 익은 토마토들이 각자의 위치에서 동시에 토마토를 익히는 경우가 고려되지 않는다. 결과적으로 답이 정답보다 커지는 오류가 일어나게 된다.

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

int m, n, ans = 0;
int tmt[1000][1000];
int day[1000][1000]; // 방문 안했으면 -1, 방문했으면 day 수 기록
vector<pair<int, int>> start;
int dx[4] = { -1, 1, 0, 0 }; → 상하좌우
int dy[4] = { 0, 0, -1, 1 }; ↗
queue<pair<int, int>> q;

void bfs()
{
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && day[nx][ny] == -1 && tmt[nx][ny] == 0)
			{
				q.push({ nx, ny });
				day[nx][ny] = day[x][y] + 1;
				ans = max(ans, day[nx][ny]);
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> m >> n;
	// 토마토 맵 초기화, day배열 -1로 초기화(접근이 안된 상태)
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			day[i][j] = -1;
			cin >> tmt[i][j];
		}
	}
	// 익은 토마토가 있고 아직 접근이 안된 상태면 큐에 push!
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (tmt[i][j] == 1 && day[i][j] == -1)
			{
				q.push({ i, j });
				day[i][j] = 0;
			}
		}
	}
	// bfs로 토마토 익히기 (day배열 수정해주기)
	bfs();
	// 예외 처리
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (tmt[i][j] == 0 && day[i][j] == -1) // 안익은 토마토가 존재!
			{
				cout << "-1" << '\n';
				return 0;
			}
		}
	}
	// 결과 출력
	cout << ans << '\n';
	return 0;
}