토마토 (feat. 백준, 7576번)

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

7576번: 토마토

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int M, N, arr[1000][1000], dx[4], dy[4];
void bfs() {
	register int x, y;
	queue<pair<int, int>> q;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < M; ++j)
			if (arr[i][j] == 1)
				q.push(make_pair(i, j));
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		x = p.first, y = p.second;
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (0 <= nx && nx < N && 0 <= ny && ny < M && arr[nx][ny] == 0)
				arr[nx][ny] = arr[x][y] + 1, q.push(make_pair(nx, ny));
		}
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> M >> N;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < M; ++j)
			cin >> arr[i][j];
	bfs();
	register int ans = 0;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < M; ++j)
			if (arr[i][j] == 0)
				cout << -1 << "\n", exit(0);
			else
				ans = max(ans, arr[i][j]);
	cout << ans - 1;
	return 0;
}
// *&)*@*

1. 최소 거리 또는 최소 일수 와 같은 문제는 BFS로 풀어야 합니다. (DFS 풀이도 가능하지만 효율이 떨어집니다.)
2. 1인 토마토의 인접 칸이 0이라면, 현재의 토마토값 + 1을 해주게 되고 이는 인접 칸이 0이 없을때까지 반복됩니다.
3. 만약 종료 후, 모든 칸 중 0이 있다면 모든 토마토를 익히지는 못한 것이므로 -1을 출력합니다.
4. 그렇지 않다면 모든 칸 중 가장 큰 값에서 -1이 모든 토마토를 익힌 날짜입니다.