간단한 BFS 문제였다. 큐에 좌표와 일수를 넣어 제일 마지막으로 나오는 일수가 총 걸린 일수가 된다. 다만 출력 조건을 자세히 봐야한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다. 처음 값을 입력할 때 0이 존재하면 0을 출력하고 BFS 후에 0이 존재하면 -1을 출력하고 둘 다 아니면 일수를 출력한다.
이번 문제는 빠르게 풀었기에 따로 문제점은 없었다.
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int M, N, res = 0;
int A[1001][1001];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
queue<pair<pair<int, int>, int>> q;
void solution() {
while (!q.empty()) {
int y = q.front().first.first;
int x = q.front().first.second;
int day = q.front().second;
q.pop();
res = day;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if (A[ny][nx] == -1 || A[ny][nx] == 1) continue;
A[ny][nx] = 1;
q.push({ {ny,nx}, day + 1 });
}
}
bool tf = false;
for (int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if (A[i][j] == 0) tf = true;
}
}
if (tf) cout << -1;
else cout << res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> M >> N;
bool tf = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> A[i][j];
if (A[i][j] == 0) tf = true;
else if (A[i][j] == 1) q.push({ { i,j },0 });
}
}
if (tf) solution();
else cout << 0;
return 0;
}