백준 7576번: 토마토 C++ 코드(BFS)

//7576
#include<iostream>
#include<queue>

using namespace std;

int tomatoMap[1005][1005];
int m,n;
int cnt = 0;

struct xyLocation{
    int y;
    int x;
};

void bfs(int i[1000005], int j[1000005]){
    queue <xyLocation> qq;
    xyLocation temp;
    for(int k=0; k<cnt; k++){
        temp.y = i[k];
        temp.x = j[k];
        qq.push(temp);
    }
    while(!qq.empty()){
        xyLocation now = qq.front();
        qq.pop();
        if(0<=now.y+1 && now.y+1 <n && tomatoMap[now.y+1][now.x] == 0){
            temp.y = now.y+1;
            temp.x = now.x;
            tomatoMap[now.y+1][now.x] = tomatoMap[now.y][now.x] + 1;
            qq.push(temp);
        }if(0<=now.y-1 && now.y-1<n && tomatoMap[now.y-1][now.x] == 0){
            temp.y = now.y-1;
            temp.x = now.x;
            tomatoMap[now.y-1][now.x] = tomatoMap[now.y][now.x] + 1;
            qq.push(temp);
        }if(0<=now.x+1 && now.x+1<m && tomatoMap[now.y][now.x+1] == 0){
            temp.y = now.y;
            temp.x = now.x+1;
            tomatoMap[now.y][now.x+1] = tomatoMap[now.y][now.x] + 1;
            qq.push(temp);
        }if(0<=now.x-1 && now.x-1<m && tomatoMap[now.y][now.x-1] == 0){
            temp.y = now.y;
            temp.x = now.x-1;
            tomatoMap[now.y][now.x-1] = tomatoMap[now.y][now.x] + 1;
            qq.push(temp);
        }
    }
}

int main(){
    cin >> m >> n;
    int arry[1000005];
    int arrx[1000005];
    for(int i = 0; i<n; i++){
        for(int j=0;j <m; j++){
            cin >> tomatoMap[i][j];
        }
    }
    for(int i = 0; i<n; i++){
        for(int j=0;j <m; j++){
            if(tomatoMap[i][j] == 1){
                arry[cnt] = i;
                arrx[cnt] = j;
                cnt += 1;
            }
        }
    }
    
    bfs(arry, arrx);
    int maxresult = 0;
    int state = 0;
    for(int i = 0; i<n; i++){
        for(int j=0;j <m; j++){
            if(tomatoMap[i][j] == 0){
                state = 1;
            }
            if(maxresult < tomatoMap[i][j]){
                maxresult = tomatoMap[i][j];
            }
        }
    }
    if(state == 0){
        cout << maxresult-1;
    }else{
        cout << -1;
    }
    
    
}

 

예전에 파이썬으로 풀었다가 재채점으로 틀려서 다시 c++으로 풀었다. 이 bfs 문제의 핵심은 토마토가 여러개있을때 각 토마토에서 동시에 bfs를 진행하는 것이다. 그래서 토마토 위치를 입력받고 토마토가 있는 곳을 아예 배열로 모았다가 한번에 bfs 큐에 넣어줌으로서 해결하였다.