7576번 토마토

 기본적인 BFS 문제.

 

 1. 큐에 저장한 익은 토마토의 위치를 꺼내 네 방향의 상태를 확인한다.

 2. 익지 않은 토마토가 있다면 익은 토마토가 되고 토마토가 없다면 패스한다(return).

 3. 1,2 과정을 반복하여 모든 토마토가 익는 날짜를 구한다.

 4. 모든 과정이 끝난 후 익지 않은 토마토가 있다면(solved 함수) -1을 출력하고 그렇지 않다면 다 익은 날짜(제일 큰 cnt값)를 출력한다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX 1001
 
using namespace std;
 
typedef pair<int,int> pir;
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
int map[MAX][MAX];
int cnt[MAX][MAX];
int M,N;
queue<pir> q;
int days;
 
void bfs(){
    
    while(!q.empty()){
        
        int x = q.front().second;
        int y = q.front().first;
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x + xx[i];
            int ny = y + yy[i];
            
            if(nx<0 || ny<0 || nx>=M || ny>=N || map[ny][nx]==-1 || map[ny][nx]==1) continue;
            if(map[ny][nx]==0){
                cnt[ny][nx]=cnt[y][x]+1;
                map[ny][nx]=1;
                q.push(pir(ny,nx));
                days=max(days,cnt[ny][nx]);
            }
        }
    }
}
 
void solved(){
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(map[i][j]==0){
                days=-1;
            }
        }
    }
    cout << days << endl;
}
 
int main(){
    cin >> M >> N;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin >> map[i][j];
            if(map[i][j]==1){
                q.push(pir(i,j)); // 1 위치 저장
            }
        }
    }
    bfs();
    solved();
}