알고리즘 :: 백준 :: BFS :: 2178 :: 토마토

문제

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

문제접근

코드

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

static int N, M, tomato[1000][1000], date;
static vector<pair<int, int>> startPoint;
static constexpr int moving[4][2] {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

inline bool isSafe(int y, int x) {
	return ((0 <= y && y < N) && (0 <= x && x < M));
}
bool bfs() {
	queue<tuple<int, int, int>> q;	// [y좌표, x좌표, 시간]
	for (int i = 0; i < startPoint.size(); ++i) 
		q.push(make_tuple(startPoint[i].first, startPoint[i].second, 0));
	while (!q.empty()) {
		int y, x, t; tie(y, x, t) = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int newY = y + moving[i][0], newX = x + moving[i][1];
			// 범위 내의 좌표이며 아직 익지않은 토마토인 경우에만 진행한다.
			if (isSafe(newY, newX) && tomato[newY][newX] == 0) {
				tomato[newY][newX] = 1;	// [중요!] 미리 기록하지 않으면 큐 메모리 폭발.
				q.push(make_tuple(newY, newX, t + 1));
			}
		}
		date = max(date, t);	// 최대 날짜 기록
	} 
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
			if (tomato[i][j] == 0) return false;
	return true;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> M >> N;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j) {
			int input = 0;	cin >> input;
			tomato[i][j] = input;
			// 입력을 받음과 동시에 '1'을 찾아서 시작 지점을 기록해둔다.
			if (input == 1) startPoint.push_back(make_pair(i, j));
		}
	if (bfs()) cout << date << '\n';
	else cout << -1 << '\n';
}

결과