[#7576] 토마토

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
 
    vector<vector<int>> tomato(n + 1, vector<int>(m + 1));
    int totalTomato = 0; //익어야하는 토마토의 갯수
    int currentTomato = 0;  //현재 익은 토마토의 갯수
    queue<pair<int, int>> q;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &tomato[i][j]);
 
            if (tomato[i][j] != -1)
                ++totalTomato;  //토마토가 없는 곳 빼고는 다 익어야 함
            if (tomato[i][j] == 1) {
                ++currentTomato;
                q.push(make_pair(i, j));
            }
        }
    }
 
    int yesterdayTomato = currentTomato;  //yesterdayTomato는 전날에 익은 토마토의 갯수. q에서 yesterdayTomato개만큼 pop하면서 주변 보면 됨
    int ans = 0;
 
    while (true) {
        if (currentTomato == totalTomato)
            break;  //다 익었으면 loop 탈출
 
        ++ans;
        int temp = currentTomato;  //-1로 막혀있는지 여부 확인을 위해서. 나중에 currentTomato가 변하지 않았다면(temp)와 같다면 -1 출력하고 종료해야 함
        int todayTomato = 0;  //오늘 하루동안 익은 토마토의 갯수. 나중에 yesterdayTomato에 저장
 
        for (int yesterday = 0; yesterday < yesterdayTomato; yesterday++) {
            //어제 하루동안 익은 토마토갯수만큼 pop
            int row = q.front().first;
            int col = q.front().second;
            q.pop();
 
            if (row - 1 >= 1 && tomato[row - 1][col] == 0) {
                tomato[row - 1][col] = 1;  //위
                q.push(make_pair(row - 1, col));
                ++currentTomato;
                ++todayTomato;
            }
            if (row + 1 <= n && tomato[row + 1][col] == 0) {
                tomato[row + 1][col] = 1;  //아래
                q.push(make_pair(row + 1, col));
                ++currentTomato;
                ++todayTomato;
            }
            if (col - 1 >= 1 && tomato[row][col - 1] == 0) {
                tomato[row][col - 1] = 1;  //왼쪽
                q.push(make_pair(row, col - 1));
                ++currentTomato;
                ++todayTomato;
            }
            if (col + 1 <= m && tomato[row][col + 1] == 0) {
                tomato[row][col + 1] = 1;  //오른쪽
                q.push(make_pair(row, col + 1));
                ++currentTomato;
                ++todayTomato;
            }
        }
        yesterdayTomato = todayTomato;
        if (currentTomato == temp) {
            //변하지 않았으면 더이상 -1로 막혀서 더이상 익지 못하는것
            ans = -1;
            break;
        }
    }
 
    printf("%d", ans);
 
    return 0;
}

 

처음에는 익은 모든 토마토에 대해 주변을 익혔는데 시간초과가 떠서

전날 익은 토마토만 보면서 주변을 익힘