[백준] 7576 토마토

[백준7576]토마토

전형적인 BFS 문제였다.
단, 익은 토마토가 1개 이상일 수 있기 때문에 동시다발적으로 진행되어야 한다는 점이 약간 까다로웠다.
그래서 큐에 토마토의 좌표와 익는데 걸리는 시간을 포함해주고, bfs 시작 전에 익은 토마토는 모두 큐에 넣었다.

종료 조건은,
1) 토마토가 모두 다 익는데 걸리는 시간 출력하고 종료
2) 만약 이미 저장될 때 부터 모든 토마토가 다 익어있으면 0을 출력하고 종료 -> if((전체-빈공간)==익은 토마토 수)
3) 모두 익히지 못했을 경우 -1을 출력하고 종료
->bfs 탐색 후 찾음

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

int N, M;
int map[1000][1000];
int visit[1000][1000];
queue<pair<pair<int, int>, int>> q; //위치, 토마토가 익는데까지 걸린 시간
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int date;

int BFS() { //탐색 시작
	int x, y, d;
	while (!q.empty()) {
		//큐의 가장 앞에있는 노드 꺼내기
		x = q.front().first.first;
		y = q.front().first.second;
		d = q.front().second;
		q.pop();

		//현재 노드에 인접한 모든 노드 탐색
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			//맵을 벗어나지 않고
			if (nx >= 0 && nx < N&&ny >= 0 && ny < M) {
				//익지 않은 토마토이면서 방문한 적 없다면 q에 push
				if (map[nx][ny] == 0 && visit[nx][ny] == 0) {
					q.push(make_pair(make_pair(nx, ny), d + 1));
					visit[nx][ny] = 1;
					//익은 것 체크
					map[nx][ny] = 1;
				}
			}
		}
	}
	
	return d;
}

int main() {
	int Tomato = 0;
	int Empty = 0;

	scanf("%d %d", &M, &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1) {
				Tomato++;
			}
			else if (map[i][j] == -1) {
				Empty++;
			}
		}
	}

	//이미 저장될 때 부터 모든 토마토가 다 익어있으면 1을 출력하고 종료
	if ((M*N) - Empty == Tomato) {
		printf("0\n");
		return 0;
	}

	//익은 토마토들을 동시에 진행해야하기 때문에 익은 토마토는 모두 큐에 넣기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 1) {
				q.push(make_pair(make_pair(i, j), 0));
				visit[i][j] = 1;
			}
		}
	}

	date = BFS();

	//만약 남아있는 익지 않은 토마토가 있다면 -1을 리턴하고 종료
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				printf("-1\n");
				return 0;
			}
		}
	}
	cout << date << '\n';

	return 0;
}