[백준] 7576번: 토마토(BFS) - C++

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

7576번: 토마토

---

#include <iostream>
#include <queue>
using namespace std;

int M,N;
int map[1000][1000];
queue<pair<int, int>> q;
bool result = false;
int days[1000][1000];
int day;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

void reset()
{
    for(int y=0;y<N;y++)
        for(int x=0;x<M;x++)
        {
            map[y][x]=0;
            days[y][x] = 0;
        }
}

void check()
{
    day = days[0][0];
    for(int y=0;y<N;y++)
        for(int x=0;x<M;x++)
        {
            if(map[y][x]==0)
            {
                result = true;
                return;
            }
            if(days[y][x]>day)
                day = days[y][x];
        }
}

void BFS(int x, int y)
{
    for(int y=0;y<N;y++)
        for(int x=0;x<M;x++)
            if(map[y][x] == 1)
                q.push(pair<int, int>(x,y));

    while(!q.empty())
    {
        int ax = q.front().first;
        int ay = q.front().second;
        q.pop();
        
        for(int d=0;d<4;d++)
        {
            int nx = ax+dir[d][0];
            int ny = ay+dir[d][1];
            if((nx>=0 && ny>=0)&&(nx<M&&ny<N))
            {
                if(map[ny][nx] == 0)
                {
                    days[ny][nx] = days[ay][ax] + 1;
                    map[ny][nx] = 1;
                    q.push(pair<int, int>(nx,ny));
                }
            }
        }
    }
}

int main()
{
    cin>>M>>N;
    reset();
    
    for(int y=0;y<N;y++)
        for(int x=0;x<M;x++)
            cin>>map[y][x];
    BFS(0,0);
    check();
    if(result) cout<<-1;
    else cout<<day;
}

 

BFS문제에서 달라지는 부분은 visited[][]배열을 사용하느냐, dist[][]배열(여기서는 days[][])을 사용하느냐가 큰 차이인 것 같다.

출력 하는 값에 따라서 체크하는 부분이 조금씩 달라진다.

 

이 문제에서는 미로 탐색 문제와 같이 길이를 저장하는 배열을 사용한다. 하지만 이때 마지막 값을 출력하는 것이 아니라 제일 큰 값을 출력해야한다. 어느 위치에서 끝날지 모르기 때문이다. 또한, 처음 시작할때 큐에는 입력받은 값이 1인 좌표를 모두 넣어주고 시작해야한다. 

한 점에서 시작하는 것이 아니라, 토마토가 있는 곳에서 동시에 시작해야하기 때문이다.