[백준] BOJ 7576 토마토(CPP)

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

7576번: 토마토

전형적인 BFS를 사용하는 문제이다.

기본적인 BFS에서 추가되는 것은 "토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다."라는 문제조건인다. 이 조건은 토마토가 들어있지 않은 칸들로 인하여 익은 토마토와 접촉 할 수 없는 토마토가 생긴다. 때문에 모든 토마토가 익었는지 판단해야한다.

반응형

#include "iostream"
#include "algorithm"
#include "queue"

using namespace std;

int M, N;

int Visit[1001][1001];
int box[1001][1001];
queue<pair<int, int>> Q;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int day = 0;

    cin >> M >> N;

    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({i, j});
                Visit[i][j] = 0;
            }else{
                Visit[i][j] = -1;
            }
        }
    }
	
    //BFS
    while (!Q.empty()) {
        pair<int, int> u = Q.front();
        Q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = u.first+ dx[i];
            int ny = u.second + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                continue;
            if (Visit[nx][ny] >= 0 || box[nx][ny] == -1)
                continue;
            Visit[nx][ny] = Visit[u.first][u.second] + 1;
            day = Visit[nx][ny];
            Q.push({nx, ny});
        }
    }
    
    //모든 토마토가 익었는지 판단하여 출력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (box[i][j] == 0 && Visit[i][j] == -1){
                cout << -1; 
                return 0;
            }
        }
    }
    
    cout << day;
    return 0;
}