백준[7576] 토마토

처음에 접근을 DFS를 이용하여 토마토 집단이 몇 개인지 알아보고 최소일을 구하는 방식으로 접근했는데

BFS에 대한 이해가 부족했던 것 같다.

 

BFS는 queue에 넣고 반복문을 통해 계산을 진행해서 출발 점이 여러 개여도 큐 안에 미리 넣기만 하면 여러 출발점에서도 동작시킬 수 있다.

 

 

#include <bits/stdc++.h>

#define MAXBOXLENGTH 1001
int toM,toN;
int inBoxSize[MAXBOXLENGTH][MAXBOXLENGTH];
queue<pair<int, int>> tomatoQ;
int tomatoMaxTime = 0;

void printResult();

void toBFS(){
    
    int dX[4] = {1,-1,0,0};
    int dY[4] = {0,0,1,-1};
    
    while(!tomatoQ.empty()){
        int x = tomatoQ.front().first;
        int y = tomatoQ.front().second;
        
        tomatoQ.pop();
        
        for(int i=0;i<4;i++){
            int mx = x + dX[i];
            int my = y + dY[i];
            
            if(mx < 0 || my < 0 || mx > toN-1 || my > toM -1)
                continue;
            
            if(inBoxSize[mx][my] == 0){
                inBoxSize[mx][my] = inBoxSize[x][y] + 1;
                if(tomatoMaxTime < inBoxSize[mx][my])
                    tomatoMaxTime = inBoxSize[mx][my];
                
                tomatoQ.push({mx,my});
            }
        }
        
    }
    
    
}

void tomato(){
    cin>>toM>>toN;
    
    for(int i=0;i<toN;i++){
        for(int j=0;j<toM;j++){
            scanf("%d",&inBoxSize[i][j]);
            if(inBoxSize[i][j] == 1){
                tomatoQ.push({i,j});
            }
        }
    }
    
    toBFS();
    
    bool tomatoExist = false;
    for(int i=0;i<toN;i++){
        int *p;
        p = find(&inBoxSize[i][0], &inBoxSize[i][toM], 0);
        if(p != &inBoxSize[i][toM]){
            tomatoExist = true;
            break;
        }
    }
    
    if(tomatoExist)
        cout<<"-1"<<endl;
    else if( tomatoMaxTime == 0)
        cout<<"0"<<endl;
    else
        cout<<tomatoMaxTime -1 <<endl;
  
    
}