BOJ 7576 토마토 - BFS

 

- 불어나는 익은 토마토.

- 최단시간을 구해야하기 때문에 BFS

- 가로X세로 잘 보자. 인덱스 조심!

- 시작점이 여러개 일 수 있기 때문에, 가능한 시작점 모두 큐에 넣는다.

 

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

7576번: 토마토

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

int M, N;
int box[1010][1010];
int visited[1010][1010];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int main(){
    scanf("%d %d", &M, &N);
    queue<pair<int, int> > q;

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            scanf("%d", &box[i][j]);
            visited[i][j] = -1; //모두 -1으로 초기화.
        
            if(box[i][j]==1){ //토마토가 익은 점은
                q.push(make_pair(i,j)); //큐에 넣는다
                visited[i][j]=0; //0으로 표시
            }
        }
    } //input end

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            //범위 내에 있을 때.
            if(nx<N && nx>=0 && ny<M && ny>=0){

                //토마토 아직 안 익은 경우
                if(box[nx][ny]==0 && visited[nx][ny]==-1){

                    //-1에서 그 순간의 날짜로 업데이트하고 , 큐에 넣는다.
                    visited[nx][ny] = visited[x][y] + 1;
                    q.push(make_pair(nx,ny));
                }
            }   
        }
    }

    int result=0;
    bool ch = false;

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if (box[i][j]==0 && visited[i][j]==-1){
                result = -1;
                ch = true;
                break;
            }
            else{
                result = max(result, visited[i][j]);
            }
        }
    
        if(ch) break;
    }

    printf("%d", result);
}