7576번 토마토

문제링크 : https://www.acmicpc.net/problem/7576

해결방법 : 

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 

이 문제에서 주어진 설명을 보면 하루마다 익은 토마토 좌표를 기준으로 인접한 네 방향에 안익은 토마토를 익게하므로 BFS탐색 방법을 사용하기로 생각했다. 테스트케이스에서 익은 토마토를 기준으로 따라 그려나가다 보면 이해하기 쉬울 것이다.

따라서 상자에 있는 토마토 모두가 익는데 최소의 일수는 BFS 탐색을 하고난 후의 최종적인 depth(깊이) 값이다. (그림참고)

프로그램 로직은 크게 bfs 탐색 전후로 나눌수있는데,

탐색 전에서는 입력을 받는 가운데 map에서 -1값을 갖고있으면 해당 좌표를 방문처리를 미리 해버렸다.그리고 1값을 가진 토마토 익은 기준좌표를 queue에 넣고 이좌표 또한 방문 처리를 해준다. 그리고 한번 전체를 탐색해서 이미 다 익었는지를 확인하고 다익었으면 0을 출력하고 아니면 bfs 탐색을 시작하게 했다.

bfs를 탐색한 후에는 visit배열을 보고 0이 하나라도 남아있다면 -1 출력하고 아니라면 bfs탐색에서 구한 depth값을 출력했다.

소스코드)

#include<iostream>
#include<queue>
 
using namespace std;
struct pos
{
    int x;
    int y;
};
int visit[1001][1001];
int map[1001][1001];
int M,N;
queue< pair<pos, int> > q;
int dx[4] = {-1,1,0,0}; //상하좌우 0,1,2,3 
int dy[4] = {0,0,-1,1};
bool isInMap(int x, int y)
{
    if(x <0 || x >=N || y<0 || y>=M)
    {
        return false;
    }
    else
        return true;
}
int bfs(void)
{
    pos p;
    int dep;
    while(!q.empty())
    {
        int nx = q.front().first.x;
        int ny = q.front().first.y;
        int ndep = q.front().second;
        dep = ndep;
        q.pop();
        for(int i =0; i< 4; i++)
        {
            int nnx = nx + dx[i];
            int nny = ny + dy[i];
            if(!isInMap(nnx,nny)) continue;
            else
            {
                if(!visit[nnx][nny])
                {
                    p.x = nnx;
                    p.y = nny;
                    visit[nnx][nny] = 1;
                    q.push(make_pair(p,ndep + 1));
                }
            }
        } 
    }
    return dep;
}
bool check()
{
    bool flag = false;
    for(int i = 0; i<N; i++)
    {
        for(int j = 0; j<M; j++)
        {
            if(visit[i][j] != 1)
            {
                flag = true;
                break;
            }
        }
        if(flag)
        break;
    }
    return flag;
}
int main()
{
    pos p;
    int ret;
    bool flag = false;
    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)
                visit[i][j] = 1;
            if(map[i][j] == 1)
            {
                visit[i][j] = 1;
                p.x = i;
                p.y = j;
                q.push(make_pair(p,0)); // 익은 사과의 좌표정보와 depth 값 push 
            }
        }
    }
    flag = check();
    if(flag == false)
    {
        printf("0\n");
    }
    else
    {
        ret = bfs();
        flag = check();
        if(flag){ 
            printf("-1\n");
        }
        else
        {
            printf("%d\n",ret);
        }
    }
    return 0;
}