[백준] 7576번. 토마토 (C++)

문제

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

 

풀이

흔한(?) bfs 문제이다

 

INPUT

입력하면서 모두 이미 익었는지 확인하고(isAlreadyComplete)

그렇다면 0출력 후 끝낸다

익지 않은 것이 있다면 q에 하나씩 넣어준다.

거기부터 탐색 할 것이기 때문이다

 

 

CHECK

익은 토마토의 상하좌우를 확인할 것이다.

 

단 확인하려는 위치가 토마토 판 범위를 넘어가거나

 if(nextY<0 || nextX<0 || nextY>=n || nextX>=m)  

익지 않은 토마토가 아닌 경우(비어있거나 익은 경우), 혹은 이미 방문한 곳인 경우

if(Tomato[nextY][nextX]!=0 || Visited[nextY][nextX]==1)

넘어가고 확인하지 않을 것이다

 

 

RESULT

Tomato에서 익지 않은 것이 있는지 확인하고 그렇다면 0을 출력한다.

다 익었다면 Tomato에서 가장 큰수-1 이 정답이다.

-1해주는 이유는 처음에 토마토가 익은것을 1로 표현했기 때문이다.

코드

#include<iostream>
#include <queue>
#include <string>
#include <map>
using namespace std;

int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int main()
{
    //INPUT//////////////////////////////////////////
    int n,m; cin>>m>>n;
     
    vector<vector<int>> Tomato(n,vector<int>(m));
    vector<vector<int>> Visited(n,vector<int>(m,0));
    
    queue<pair<int,int>>q;
    
    bool isAlreadyComplete=true;
    for(int i=0;i<n;i++)
    {
        for(int k=0;k<m;k++)
        {
            cin>>Tomato[i][k];
            if(Tomato[i][k]==1){q.push({i,k});}
            else{isAlreadyComplete=false;}
        }
    }
    
    if(isAlreadyComplete){cout<<0; return 0;}

    int result=0;
    
    //CHECK////////////////////////////////////////////
    while(!q.empty())
    {
        int nowY=q.front().first;
        int nowX=q.front().second;
        
        q.pop();
        
        for(int i=0;i<4;i++)
        {
            int nextY=nowY+dir[i][1];
            int nextX=nowX+dir[i][0];
            
            if(nextY<0 || nextX<0 || nextY>=n || nextX>=m) continue;
            if(Tomato[nextY][nextX]!=0 || Visited[nextY][nextX]==1) continue;
            
            Visited[nextY][nextX]=1;
            Tomato[nextY][nextX]=Tomato[nowY][nowX]+1;
            q.push({nextY,nextX});
            
        }
    }
    
    //RESULT/////////////////////////////////////////
    //전부다 익지 못한 경우 확인
    for(int i=0;i<n;i++)
    {
        for(int k=0;k<m;k++)
        {
            if(Tomato[i][k]==0){cout<<-1; return 0;}
        }
    }

    //결과 확인
    for(int i=0;i<n;i++)
    {
        for(int k=0;k<m;k++)
        {
            if(result<Tomato[i][k])
            {result=Tomato[i][k];}
        }
    }
    
    cout<<result-1;
}