[백준] 7576번 토마토 (c)

출처

한국정보올림피아드 지역본선 2013 고등부 1번

문제 번호

백준 7576번 토마토
코드업 4781 : 토마토(고등)

힌트

배열에 토마토가 익는 날짜를 저장

 

 

풀이

이 문제 풀이의 핵심은 배열에 토마토가 익는 날짜를 저장한다는 것이다. 익은 토마토의 입력이 1로 들어오기 때문에 day배열에 저장될 숫자는 그 위치의 토마토가 익는 날 +1이 된다. 토마토의 위치를 나타낼 dot 구조체를 만들어주고 dot을 넣을 큐q를 만들어 준다. BFS이기 때문에 가장 먼저 갱신된 값이 날짜의 최소값이다. 따라서 check배열을 만들어 주지 않고 day배열을 check배열처럼 사용할 수 있다.
BFS가 끝나고 day배열에 들어있는 최대값을 찾으면 된다. 만약 0이 남아 있다면 익지 않고 남아있는 토마토가 있는 것이기 때문에 ans를 0으로 바꿔주고 반복문을 탈출한다.day배열에 들어있는 숫자는 그 위치의 토마토가 익는 날 +1이기 때문에 우리가 구한 최대값에서 1을 빼고 출력을 해주어야 한다,

#include<iostream>
#include<queue>
using namespace std;
int day[1000][1000];


int n,m;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

typedef struct dot{
    int x,y;
};

queue<dot> q;


int main(){

    cin>>n>>m;

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>day[i][j];
            if(day[i][j]==1){
                q.push({i,j});
            }
        }
    }

    int date=2;
    while(!q.empty()){
        int size = q.size();
        for(int i=0;i<size;i++){

            int a=q.front().x,b=q.front().y;
            q.pop();

            for(int j=0;j<4;j++){
                int na=a+dir[j][0],nb=b+dir[j][1];
                if(na>=m||nb>=n||na<0||nb<0||day[na][nb]!=0)
                    continue;

                day[na][nb]=date;
                q.push({na,nb});
            }    

        }
        date++;
    }


    int ans=0, flag=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(day[i][j]==0){
                flag=1;
                ans=0;
                break;
            }
            ans=max(ans,day[i][j]);
        }

        if(flag)
            break;
    }
    cout<<ans-1;


}

백준 토마토

코드업 토마토