백준 7576번 - 토마토

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

처음에 이 문제를 보면서 dfs로 근접한 4개의 상자를 방문하는 식으로 생각했다.


그런데 문제를 읽으면서 토마토가 있는 상자를 발견했을 때, 
그 부분에서 깊이 탐색으로 인접한 부분을 계속해서 탐색을 하는 것이 아니라 인접한 부분의 위치를 저장하는 문제였다. 
그리고 다음번에 저장한 부분의 위치를 가져온 다음에 다시 주변에 인접한 부분을 검사하는 방식이다.


즉, 큐에다가 익은 토마토의 인접한 부분에 익지 않은 토마토의 위치 정보를 담아내고 
이 위치에 있는 토마토를 익은 토마토로 변경한다. 그리고 다시 이 작업을 반복하여 더 이상 담아낼 수 있는 상자가 없을 때 종료하는 것이다.



문제를 푸는데 한 시간 정도가 걸렸는데..
내가 미처 생각하지 못한 부분이 없는지 검토하고 추가하는 데 시간이 좀 오래 걸린 것 같다.


먼저 저장될 때부터 모든 토마토가 익은 경우, 문제의 조건에 따라 바로 0을 출력하고 종료했다. 

그 이유는 밑에서 익은 토마토의 인접 부분을 모두 검사하는 것을 피하기 위해서다.



다음으로 인접한 부분을 검사하는 while 문 내에서
익은 토마토 상자를 방문하여 검사한 부분은 visited를 통해 다시 방문하지 않도록 했다. 

익은 토마토가 있는 위치 정보를 q 변수에 담고 q가 비어 있을 때까지 반복한다. 

만약에 주변의 인접한 부분에 아직 익지 않은 토마토가 있다면 q2라는 새로운 큐에 담아낸다. 

그리고 q가 비어있을 때까지 작업을 완료하면 검사한 횟수를 1번 증가시킨 다음에 q2에 있는 위치 정보를 다시 q에 담아서 위의 작업을 반복했다.



마지막으로 검사를 모두 마친 뒤에 익지 않은 토마토가 있는지 확인한 후, 있다면 -1을 출력해주면 된다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
 
int main(){
    
    int M,N;
    cin>>M>>N;
    
    vector<vector<int>> arr(N,vector<int>(M,0)); //상자
    vector<vector<int>> visited(N,vector<int>(M,0)); //토마토 들어있는 상자 방문 유무
    queue<pair<int,int>> q;
    
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++){
            scanf("%d",&arr[i][j]);
            if(arr[i][j]==1){
                q.push(make_pair(i,j));
                visited[i][j]++;
            }
 
        }
    
    //저장될 때부터 모두 익은 경우
    if(q.size()==M*N){
        cout<<0<<endl;
        return 0;
    }
 
    int ans=0;
    while(true){
        
        //토마토가 익은 위치의 인접한 부분에서 아직 익지 않은 토마토가 있을 때
        queue<pair<int,int>> q2;
 
        while(!q.empty()){
            int y=q.front().first;
            int x=q.front().second;
            q.pop();
            
            for(int dir=0;dir<4;dir++){
                int ny=y+dy[dir];
                int nx=x+dx[dir];
                
                if(ny<0 || ny>=N || nx<0 || nx>=M)
                    continue;
                
                if(visited[ny][nx] || arr[ny][nx]!=0)
                    continue;
                
                visited[ny][nx]++;
                arr[ny][nx]=1;
                q2.push(make_pair(ny,nx));
            }
        }
        
        q=q2;
        if(q.empty()) //더이상 확인할 토마토 없는 경우
            break;
        
        
        ans++;
    }
    
    //익지 못한 토마토 있는지 확인
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            if(arr[i][j]==0){
                ans=-1;
                break;
            }
    
    
    cout<<ans<<endl;
    
    return 0;
}