[백준 7576] 토마토

🔗알고리즘 문제

BFS문제는 항상 문제가 직관적으로 생각할 수 있어서 재밌고 풀기 쉬운 것 같다.

문제 분석

이 문제는 토마토 창고에 들어있는 토마토들의 정보가 주어질 때 모든 토마토가 익는데 며칠이 걸리는지 알아내는 문제이다.

이 때 하루가 지나면 익은 토마토의 상하좌우 방향에 있는 토마토들이 익게 된다.

발상 & 알고리즘 설계

체크 해야하는 좌표를 queue에 담아주며 queue가 비어있을 때 까지 해당 좌표에 상하좌우를 탐색해주었다.

이때 상하좌우가 익은 토마토가 될 때 까지 걸리는 시간은 중앙에서 하루가 지날 때 이므로 중앙값 + 1을 해주었다.

코드

#include<iostream>
#include<queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int box[1000][1000] = {};

    int destX[4] = { 0, 0, -1, 1 };
    int destY[4] = { -1, 1, 0, 0 };

    int n;
    int m;

    int day = 0;

    queue<pair<int, int>> check;

    cin >> n >> m;

    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            cin >> box[i][j];

            if(box[i][j] == 1)
            {
                check.push({ j , i });
            }
        }
    }

    while(check.empty() == false)
    {
        pair<int, int> node = check.front();
        check.pop();

        for(int i = 0; i < 4; ++i)
        {
            int x = node.first + destX[i];
            int y = node.second + destY[i];

            if(x < 0 || x >= n || y < 0 || y >= m)
                continue;
            if(box[y][x] == -1)
                continue;
            if(box[y][x] != 0 && box[y][x] <= box[node.second][node.first] + 1)
                continue;

            box[y][x] = box[node.second][node.first] + 1;
            check.push({ x, y });
        }
    }   

    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            if(box[i][j] == 0)
            {
                cout << -1;
                return 0;
            }

            if(box[i][j] > 0)
            {
                day = max(day, box[i][j]);
            }
        }
    } 

    cout << day - 1;
}