[백준 7576] 토마토(2차원)

백준 7576 토마토

이 문제는 익은 토마토가 주변 익지 않은 토마토를 익게 만든다. 박스 안에 토마토의 정보를 받으면서 익은 토마토의 위치를 큐에 넣고 큐 사이즈만큼 돌면서 큐의 크기가 0이 될 때까지 돌리면 된다.

이때까지 포스트를 올린 문제는 대부분 두 가지 유형으로 볼 수 있다.

이 문제에서 우리가 중심적으로 봐야하는 익은 토마토나 불이나 불! 문제에서 우리가 봐야하는 불이랑 사람의 위치를 알아야 하고 BFS를 돌리면서 주변으로 퍼지게 하는 느낌으로 짜면 된다.

이러한 문제와 다르게 단지번호붙이기, 유기농 배추와 같은 문제는 한 좌표에서 주변으로 퍼져나가 넓이를 계산하고 다른 좌표(방문하지 않았던 좌표)에서 또 퍼져나가면서 넓이를 구하는 문제가 있다.

하지만 두 가지 유형엔 공통점이 있다. 바로 한 중심의 좌표에서 주변으로 퍼져나가는 것이다. 이게 핵심 포인트이다. 한 중심으로부터 퍼져나가는 성질을 이용하면 우리가 가야하는 목적지까지 최단거리를 구할 수 있다.

#include<cstdio>
#include<queue>
 
using namespace std;
 
queue<pair<int, int>> q;
int map[1001][1001] = { 0 };
bool visit[1001][1001] = { 0 };
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
 
int main()
{
    int n, m;
    scanf("%d %d", &m, &n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 1)
            {
                q.push(make_pair(i, j));
                visit[i][j] = true;
            }
            else if (map[i][j] == -1)visit[i][j] = true;
        }
    }
 
    int ans = -1;
 
    while (!q.empty())
    {
        int size = q.size();
        ans++;
        while (size--)
        {
            pair<int, int> now = q.front(); q.pop();
            for (int k = 0; k < 4; k++)
            {
                int qx = now.second + dx[k];
                int qy = now.first + dy[k];
                if (qx >= 0 && qx < m && qy >= 0 && qy < n)
                {
                    if (!visit[qy][qx] && !map[qy][qx])
                    {
                        visit[qy][qx] = 1;
                        q.push(make_pair(qy, qx));
                    }
                }
            }
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (!visit[i][j])return !printf("-1");
        }
    }
    printf("%d", ans);
    return 0;
}