[BFS, 난이도 중하] 백준 7576번 토마토

https://kimcoder.tistory.com/16

[BFS, 난이도 하] 백준 2178번 미로 탐색

미로 탐색 문제처럼 time 배열을 쓸것이다.

다시 한번 설명 하지만, time배열은 각 좌표의 토마토가 언제 익게 되었는지의 시각을 의미 한다.

미로 탐색 문제와 다른 점은 시작점이 꼭 하나는 아니라는 것이다.

즉, BFS의 while문을 수행하기 전에 큐에 여러 좌표를 넣고 시작할 수도 있다는 것이다.

 

이 것 외의 차이점 하나가 더 있는데 예외 처리를 해야 한다.

모든 토마토가 익지 않았을 때는 -1을 출력해야 한다.

 

그러나 어렵지 않다.

큐에 더 이상 아무것도 남아 있지 않을 때 while문을 빠져 나오게 되는데

이 때 최종 time 배열을 확인하면 된다.

이 time배열의 값이 0이면서 빈칸(map배열의 값이 -1)이 아니라면, 즉 익지 않은 토마토가 남아 있을 경우 -1을 출력하고 바로 프로그램을 종료하면 된다.

 

아래 표는 예제 입력 2 케이스의 내가 작성한 코드에서 time 배열이다.

만약 모든 토마토가 익은 케이스였다면 time배열 요소의 최댓값 - 1 이 정답이다.

-1을 해주는 이유는 최초에 이미 익은 토마토의 time배열 값을 1로 시작해서이다.

 

좌표(0,0)은 토마토가 있는데(빈칸이 아닌데) 익지 않았기 때문에(방문하지 않았기 때문에) -1을 출력하고 탈출.

좌표(0,0) 만 확인해도 이 경우의 출력값은 -1인것을 바로 확인했다. 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int map[1001][1001];
int time[1001][1001];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	queue<pair<int, int> > q;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) {
				time[i][j] = 1;
				q.push(make_pair(i, j));
			}
		}
	}
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			if (x + dx[i] < 0 || x + dx[i] >= m || y + dy[i] < 0 || y + dy[i] >= n) continue;
			if (map[x + dx[i]][y + dy[i]] == 0 && !time[x + dx[i]][y + dy[i]]) {
				q.push(make_pair(x + dx[i], y + dy[i]));
				time[x + dx[i]][y + dy[i]] = time[x][y] + 1;
			}
		}
	}
	int maxi = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (time[i][j] == 0 && map[i][j] != -1) {
				cout << "-1";
				return 0;
			}
			if (time[i][j] > maxi) maxi = time[i][j];
		}
	}
	cout << maxi - 1;
}