백준 '토마토' 문제 보러가기

그 날에 어떤 토마토가 익었는지 구분하는 방법을 잘 떠올리면 어렵지 않게 풀 수 있는 문제였다.

소스 코드

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int M,N, cnt=0, result=0;
int xDir[4]={0,0,-1,1}, yDir[4]={1,-1,0,0};
queue<pair<int,int>> q;

int main() {
    cin >> M >> N;
    int box[N][M];
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>box[i][j];
            if(box[i][j]==1) q.push(make_pair(i,j));
            
            else if(box[i][j]==0) cnt++;
        }
    }
    
    while(!q.empty()){
        pair<int, int> e;
        e = q.front();
        q.pop();

        for(int i=0;i<4;i++){
            int xPos = e.second+xDir[i], yPos=e.first+yDir[i];
            if(xPos < 0 || xPos > M-1 || yPos <0 || yPos > N-1) continue;
            if(box[yPos][xPos]==0){
                box[yPos][xPos]=box[e.first][e.second]+1;
                q.push(make_pair(yPos,xPos));
                cnt--;
            }
        }
    }

    for(int k=0;k<N;k++)
        for(int z=0;z<M;z++)
            if(box[k][z] > result) result = box[k][z];
            
    if(cnt != 0) result = -1;
    else result-=1;
    cout<<result;

}

내가 적용한 토마토 구분 방법은 아래와 같다.

이미 숙성된 토마토는 표에 1로 표시된 김에 해당 토마토를 첫째 날에 익은 토마토로 간주했다. 해당 토마토를 중심에 두고 추후 숙성되는 주변의 토마토는 중심 토마토에 적힌 날짜를 기준으로 1씩 증가하면서 몇번째 날에 익은 토마토인지를 표시해준다.

BFS가 종료되고 가장 큰 값을 찾아 해당 값에서 1을 빼서(문제에서는 모두 익는데 걸리는 날짜를 물어봤기 때문이다.) 출력하면 토마토가 모두 익는데 걸리는 날 수를 출력하게 된다.