[백준 c++] 7576 토마토

문제

https://www.acmicpc.net/problem/7576
N x M 크기의 격자 모양 상자의 칸에 토마토를 하나씩 넣어서 창고에 보관한다. 익은 토마토의 4방향으로 인접한 토마토는 하루가 지나면 익게 된다. 익은 토마토는 1, 익지 않은 토마토는 0, 토마토가 없는 칸은 -1로 주어진다.
이 때 모든 토마토가 익는 최소 일 수를 구하는 문제다.

풀이

BFS

한 방향으로 끝까지 탐색하는 DFS는 이 문제에 적합하지 않다.
4방향으로 1 레벨씩 탐색해야하기 때문에 현재 노드에 인접한 노드를 탐색하는 BFS가 적합하다.

🌟 BFS의 최초 시작지점인 익은 토마토가 여러 개 일 수 있다.
이럴 때는 입력을 받을 때부터 큐에 시작지점을 다 넣어두면 된다.

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

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, y, x, res, map[1001][1001], dy[4] = {-1, 0, 1, 0}, dx[4] = {0, -1, 0, 1};
queue<pair<int, int>> q;

void bfs()
{
    while (q.size())
    {
        tie(y, x) = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;

            if (map[ny][nx] == 0)
            {
                map[ny][nx] = map[y][x] + 1;
                q.push({ny, nx});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    bfs();

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] == 0)
            {
                cout << "-1";
                return 0;
            }
            res = max(res, map[i][j]);
        }
    }
    cout << res - 1;
}