토마토 — 다중 시작점 BFS + 센티널로 날짜 세기 (BOJ 7576)

아이디어

• 모든 익은 토마토(1)를 초기 큐에 넣고, 방문(vis)을 1로 표시.
• 빈 칸(-1)은 애초에 방문 처리해서 나중에 미방문 검사에서 제외.
• 하루 경계를 잡기 위해 큐에 **센티널 (-1,-1)**을 넣고, 레벨이 끝날 때마다 ans++.
• 확장은 **adj==0(안 익은 토마토)**만 대상으로 4방향 BFS.

알고리즘

1. 입력에서 1이면 큐에 넣고 vis=1, -1이면 vis=1.

2. 큐에 센티널 (-1,-1) 추가, ans=-1로 시작(첫 레벨 처리 후 0일이 되도록).

3. BFS:

   • 보통 좌표는 인접 4칸으로 확장(범위·방문·값 체크).
   • 레벨이 끝나면(다음 원소가 센티널) 센티널을 빼고 다시 넣으며 ans++.

4. 종료 후 vis==0이 남아 있으면 -1, 아니면 ans 출력.

복잡도

• 시간: O(n·m)
• 공간: O(n·m)

코드

#include <bits/stdc++.h>
using namespace std;

int adj[1002][1002];
int vis[1002][1002];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> m >> n;

    queue<pair<int, int>> q;
    int ans = -1;
    int err = 0;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> adj[i][j];
            if (adj[i][j] == 1)
            {
                q.push({i, j});
                vis[i][j] = 1;
            }
            if (adj[i][j] == -1)
            {
                vis[i][j] = 1;
            }
        }
    }
    q.push({-1, -1});

    while (!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;
            if (vis[nx][ny] || adj[nx][ny] != 0)
                continue;
            vis[nx][ny] = 1;
            q.push({nx, ny});
        }
        if (!q.empty() && q.front().first == -1)
        {
            q.pop();
            q.push({-1, -1});
            ans++;
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (vis[i][j] == 0)
            {
                err = 1;
                break;
            }
        }
    }

    if (err)
    {
        cout << -1;
    }
    else
        cout << ans;

    return 0;
}

메모

• ans=-1로 두는 건 초기 상태가 이미 모두 익은 경우 정답이 0이 되도록 하기 위함.
• 센티널 대신 for(size=Q.size()) 레벨 루프를 써도 동일하게 풀 수 있음.