[백준] 7576 토마토

문제 설명

https://www.acmicpc.net/problem/7576

7576번: 토마토

익은 토마토들의 상하좌우로 인접한 곳에 있는 익지 않은 토마토는 익게 된다

따라서 최소 며칠이 지나면 토마토들이 모두 익는지 구하기

 

문제 풀이법

토마토가 다 익기까지 필요한 최소 일수를 구하는 것은, 모든 익지 않은 토마토들에 대해 가장 가깝게 위치한 익은 토마토까지의 거리를 구한다는 점에서 BFS로 풀어야 한다

익은 토마토는 여러개일 수 있으니, 시작점을 여러개 두어서 BFS를 돌리는 것이 핵심이다

즉, 익은 토마토가 들어오는 좌표값을 모두 큐에 넣어서 BFS를 돌린다

visited배열은 방문했는지 안했는지와 검증함과 동시에, 며칠에 걸려서 토마토가 익는지 저장할 수 있는 배열이다

따라서 이미 익은 토마토거나, 토마토가 들어있지 않으면 0, 익지 않은 토마토면 -1을 기본값을 셋팅해야한다

(들어가있지 않은 토마토를 -1로 설정했다가 틀렸다)

 

BFS를 모두 돌고난 후, visited 배열에 -1이 남아있으면 익지 않은 토마토가 있다는 뜻이므로 -1을 출력한다

 

소스 코드

#include <iostream>
#include <utility>
#include <queue>

using namespace std;

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

int main()
{
    int arr[1001][1001];
    int visited[1001][1001];
    
    int n, m;
    cin >> m >> n;
    
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
            visited[i][j] = 0;
            
            if (arr[i][j] == 1)
                q.push({i, j});
            if (arr[i][j] == 0)
                visited[i][j] = -1;
        }
    }
    
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        
        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 || visited[ny][nx] >= 0)
                continue;
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
        }
    }
    
    int max = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (visited[i][j] == -1)
            {
                printf("-1\n");
                return (0);
            }
            if (max < visited[i][j])
                max = visited[i][j];
        }
    }
    
    printf("%d\n", max);

    return 0;
}