[BOJ] 7576. 토마토

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

7576번: 토마토

이 문제는 전형적인 bfs 문제이다.

상자에 있는 토마토가 상하좌우로 하루에 하나씩 익어가는데 모든 토마토가 익는데 걸리는 최소 일수를 구해야 하므로 bfs를 사용하면 된다.

기존에 익어있는 토마토로부터 익으므로 입력받을 때 익은 토마토인 경우 바로 큐에 넣어준다.

상하좌우를 탐색하며 방문하지 않은 토마토에 방문하여 소요 날짜를 저장한다.

 

 

탐색이 끝난 이후에는 문제의 조건에 따라 토마토가 모두 익지는 못하는 상황이라면 -1을 출력하기 위해서

안 익은 토마토인데 방문하지 않은 토마토를 찾는다. 혹시 존재한다면 ans는 -1 값을 가지고 그렇지 않은 경우에는

가장 마지막 토마토가 익은 날짜가 저장된다.

 

#include <cstdio>
#include <queue>
using namespace std;
int n,m;
int box[1000][1000];
int day[1000][1000];
int dx[] = {0,0,1,-1};
int dy[] = {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]);
 
            //익는데 걸리는 날짜를 저장할 배열 -1로 초기화
            day[i][j] = -1;
 
            //익은 토마토인 경우 큐에 넣는다.
            if(box[i][j] == 1) {
                q.push(make_pair(i,j));
                day[i][j] = 0;
            }
        }
    }
 
 
    //bfs
    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 < 0 || ny < 0 || nx >= n || ny >= m) continue;
 
            //안익은 토마토 && 아직 방문 안함
            if(box[nx][ny] == 0 && day[nx][ny] == -1) {
                q.push(make_pair(nx,ny));
 
                //소요 일수를 저장 (이전 칸보다 하루 증가)
                day[nx][ny] = day[x][y] + 1;
            }
        }
 
    }
 
 
    //탐색 종료 후에 안익은 토마토가 있는지를 검사 
    int ans = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
 
            //안 익은 토마토가 있는데 방문하지 않았다.
            if(box[i][j] == 0 && day[i][j] == -1) {
                ans = -1;
                break;
            }
 
 
            //가장 마지막에 익은 토마토의 날짜를 구해야하므로
            //최댓값을 ans에 저장한다. 
            if(ans < day[i][j])
                ans = day[i][j];
        }
        //위의 반복문에서 안익은 토마토가 있는 경우 빠져나와서 break
        if(ans == -1) break;
    }
 
    printf("%d", ans);
 
    return 0;
}