백준 7576 - 토마토

문제 링크입니다 https://www.acmicpc.net/problem/7576

7576번: 토마토

 

7569 토마토 문제와는 다르게 2차원 BFS를 요구하는 문제입니다.

4방향 탐색을 위해서 arr,arr2 배열을 만들어줬습니다. 이중 for문으로 토마토를 입력받고, 익지 않은 토마토의 갯수와 익은 토마토를 큐에 넣는 작업을 동시에 했습니다.

입력이 끝나고 익지 않은 토마토의 갯수가 0개라면 바로 0을 출력해주고 0이 아니라면 BFS를 실행합니다.

BFS 탐색 중에 익지 않은 토마토를 익은 토마토로 바꿔주고, 익지 않은 토마토의 갯수를 하나 빼줍니다. 

check 배열에는 토마토가 익은 날짜가 저장됩니다. 따라서 max_day라는 변수를 선언해 check 배열의 값과 계속 비교함으로써 최소 일수를 구합니다.

마지막에 익지 않은 토마토의 갯수가 0이라면 최소 일수를 출력하고, 아니라면 -1를 출력하면 됩니다

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;
int tomato[1001][1001];
int check[1001][1001];
int number_tomato;
typedef struct qu {
	int x;
	int y;
}qu;
queue<qu> q;
int arr[4]  = { 1,0,-1,0 };
int arr2[4] = { 0,-1,0,1 };
int M, N;
int max_day;

void bfs() {
	while (!q.empty()) {
		int x1 = q.front().x;
		int y1 = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x1 + arr[i];
			int yy = y1 + arr2[i];
			if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
				if (check[xx][yy] == 0 && tomato[xx][yy] == 0) {
					check[xx][yy] = check[x1][y1] + 1;
					tomato[xx][yy] = 1;
					number_tomato--;
					max_day = max(max_day, check[xx][yy]);
					q.push({ xx,yy });
				}

			}
		}
	}
	if (number_tomato == 0) {
		cout << max_day - 1;
	}
	else {
		cout << "-1";
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> M >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> tomato[i][j];
			if (tomato[i][j] == 1) {
				check[i][j] = 1;
				q.push({ i,j });
			}
			if (tomato[i][j] == 0) {
				number_tomato++;
			}
		}
	}
	if (number_tomato == 0) cout << "0";
	else bfs();
	return 0;
}