백준 / 7576 / 토마토 / 알고리즘 문제풀이 / C++

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

7576번: 토마토

 

 

BFS를 사용해서 큐에 익힐 수 있는 조건의 토마토의 위치와 익는데까지 걸리는 날짜를 넣고 익힐 수 있는

모든 토마토를 탐색하는 방식으로 풀어보았습니다.

 

출력을 위해서 zeroCnt라는 변수를 만들어서 0의 개수를 세면서 토마토를 다 익힐수 없는경우와 

처음부터 다 익혀져있는 경우에 대해서 정상적으로 출력할 수 있도록 했습니다.

 

최종적인 날짜 출력은 max라는 변수를 만들어서 큐에있는 정보를 pop할때마다 , 갱신시켜서

마지막에는 모두 익힐때까지 걸린 총 날짜를 출력할 수 있도록 했습니다.

#include <iostream>
#include <queue>
#include <algorithm>
 
using namespace std;
 
struct tomato
{
    int xPos;
    int yPos;
    int day;
    tomato(int x, int y, int z)
    {
        xPos = x;
        yPos = y;
        day = z;
    }
 
};
 
int M, N;
int zeroCnt = 0;
int tomatoStatus[1000][1000];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
queue<tomato> Q;
 
 
void bfs()
{
    int max = 0;
 
    while (!Q.empty())
    {
        auto cur = Q.front();
        max = cur.day;
        Q.pop();
 
 
        for (int i = 0; i < 4; i++)
        {
            int newX = cur.xPos + dx[i];
            int newY = cur.yPos + dy[i];
 
            if (tomatoStatus[newX][newY] == 0 && newX < N && newX >= 0 && newY >=0 && newY < M)
            {
                zeroCnt--;
                Q.push({ newX,newY,cur.day + 1 });
                tomatoStatus[newX][newY] = cur.day + 1;
            }
        }
 
    }
 
    if (zeroCnt > 0)
        cout << "-1" << endl;
    else
        cout << max << endl;
 
}
 
int main()
{
    cin >> M >> N;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> tomatoStatus[i][j];
            if (tomatoStatus[i][j] == 0)
                zeroCnt++;
            if (tomatoStatus[i][j] == 1)
                Q.push({ i,j,0 });
            
        }
    }
    if (zeroCnt == 0)
    {
        cout << "0" << endl;
        return 0;
    }
        
    
    bfs();
 
 
    return 0;
}