[c++] 백준 7576: 토마토

7576번: 토마토

문제

코드

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
#define fio ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

queue<pair<int, int>> q;
queue<pair<int, int>> tmp;

int main(){
    //input
    fio;
    int m, n; cin >> m >> n;
    int tomato[n+2][m+2];
    memset(tomato, -1, sizeof(tomato));

    int no_tomato_num = 0;
    int tomato_num = 0;
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> tomato[i][j];

            if (tomato[i][j] == 1) { // 익음
                q.push(make_pair(i, j));
                tomato_num++;
            }

            if (tomato[i][j] == -1) { // 토마토 없음
                no_tomato_num++;
            }
        }
    }

    //solution
    int date = 0;
    
    if (no_tomato_num == (n * m)) { // 모두 토마토 아님
        cout << -1;
    }

    else if ((tomato_num + no_tomato_num) == (n * m)){ // 익은 토마토만 있음
        cout << 0;
    }

    else
    {
        while (!q.empty())
        {
            tmp = q;
            q = queue<pair<int, int>>(); // 다음 단계를 위해 비움.

            while (!tmp.empty())
            {
                int tmp_i = tmp.front().first;
                int tmp_j = tmp.front().second;
                tmp.pop();

                if (tomato[tmp_i - 1][tmp_j] == 0)
                {
                    q.push(make_pair(tmp_i - 1, tmp_j));
                    tomato[tmp_i - 1][tmp_j] = 1;
                    tomato_num++;
                }

                if (tomato[tmp_i + 1][tmp_j] == 0)
                {
                    q.push(make_pair(tmp_i + 1, tmp_j));
                    tomato[tmp_i + 1][tmp_j] = 1;
                    tomato_num++;
                }

                if (tomato[tmp_i][tmp_j - 1] == 0)
                {
                    q.push(make_pair(tmp_i, tmp_j - 1));
                    tomato[tmp_i][tmp_j - 1] = 1;
                    tomato_num++;
                }

                if (tomato[tmp_i][tmp_j + 1] == 0)
                {
                    q.push(make_pair(tmp_i, tmp_j + 1));
                    tomato[tmp_i][tmp_j + 1] = 1;
                    tomato_num++;
                }
            }

            date++;
        }

        if (tomato_num + no_tomato_num == n * m)
            cout << date - 1;
        else
            cout << -1;
    }

    return 0;    
}

해설

토마토가 모두 익을 때까지의 최소 날짜를 출력해야 하기 때문에 BFS를 이용하였다. 우선 토마토에 대한 정보를 tomato배열로 받고, 해당 tomato가 익은 것에 대해 체크하기 위해 chk배열을 사용하였다. (하나로 줄일 수 있을 거 같음. 더 고민해보기)

우선 처음 익은 토마토를 queue(q)에 넣어 준비를 시킨다. 그 후 queue에 담긴 것을 따른 새로운 queue(tmp)에 옮긴 후 queue(q)는 비워주고, queue(tmp)의 주변 위치(위, 아래, 왼쪽, 오른쪽)의 토마토 상태가 0이면 그것을 queue(q)에 넣어주고 다음 날에 익을 수 있도록 한다. tmp의 원소가 모두 비면 그 날 하루가 끝난 것이므로 date의 값을 1 증가 시켜주고, 이를 계속 반복하여 모든 토마토가 익도록 한다.

마지막엔 다 익은 토마토와 원래 토마토가 아닌 것을 더해서 상자의 갯수만큼 만들어지면 모두 다 익은 것이므로 date를 출력해주고, 아니면 모두 익지 않은 것이므로 -1을 출력해준다.