7576번

7576번 - 토마토

한 점에서 거리가 하루(1일)로 동일하게 퍼져나가므로 BFS 문제라고 볼 수 있다. 그리고 이에 따른 최소값을 묻는 문제이므로.

처음에 익은 토마토가 있는 하나의 정점에서 BFS를 수행한다.

그리고 익지 않은 토마토가 있는 각각의 점들에 대하여 dist 값, 즉 몇일 만에 토마토가 익는지 계산해본다.

그리고 또 다른 익은 토마토가 있는 정점에서 BFS를 수행한다.

이미 예전에 방문했던 점을 경우에는 dist값을 비교하여 적은 값으로 업데이트 해준다.

이런식으로 처음에 익은 토마토가 있는 모든 점에서 BFS를 수행하면 최소값을 계산할 수 있다.

다 익지 않는 경우는 

익지 않는 토마토의 dist 값이 0 인 경우에는 모든 BFS 탐색에도 불구하고 그 토마토가 익지 않았다는 증거이므로 그에 따라 값을 출력한다.

< 정답 코드 >

#include<iostream>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,- 1,0,0 };
int map[1001][1001];
bool check[1001][1001];
int dist[1001][1001];
int main()
{
    //freopen("input.txt", "r", stdin);
    int N, M;
    cin >> M >> N;
    memset(map, 0, sizeof(map));
    memset(check, false, sizeof(check));
    memset(dist, 0, sizeof(dist));
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (map[i][j] == 1)
            {
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                check[i][j] = true;
                dist[i][j] = 0;
 
                while (!q.empty())
                {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
 
                    for (int d = 0; d < 4; d++)
                    {
                        int nx = x + dx[d];
                        int ny = y + dy[d];
                        if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny]==0)
                        {
                            if (!check[nx][ny])
                            {
                                dist[nx][ny] = dist[x][y] + 1;
                                check[nx][ny] = true;
                                q.push(make_pair(nx, ny));
                            }
                            else if (check[nx][ny])
                            {
                                if (dist[nx][ny] > dist[x][y] + 1)
                                {
                                    dist[nx][ny] = dist[x][y] + 1;
                                    q.push(make_pair(nx, ny));
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (dist[i][j] == 0 && map[i][j]==0)
            {
                ans = -1;
                break;
            }
 
            ans = max(ans, dist[i][j]);
 
        }
 
        if (ans == -1)
        {
            break;
        }
    }
    
    cout << ans << endl;
 
    return 0;
}