백준 7576 토마토 / C++

문제 : 링크텍스트

풀이 point

bfs를 활용
토마토가 익는 날짜를 세어나가야함
모든 토마토가 1이 될 경우 최소 날짜를 출력

풀이 순서

1. 입력
2. 입력을 순회하면서 익은 토마토를 만날 경우 큐에 push
3. bfs를 진행하면서 거리값을 갱신
4. bfs가 진행된 토마토를 순회하면서 익지 않은 토마토 발견 시 -1 출력
5. 최대 거리 값 갱신(이것이 최소 날짜가 됨)
6. 거리 값 출력

코드

//백준 7576, 토마토

#include <iostream>
#include <vector>
#include <queue>
#define x first
#define y second

std::queue<std::pair<int, int>> Q;
std::vector<int> dx = {-1, 0, 1, 0};
std::vector<int> dy = {0, 1, 0, -1};

int grid[1000][1000];
int dist[1000][1000];
int N, M;
int day{0};

void testprint(){
    std::cout << "--------------------------------------------" << '\n';
    for(int i{0}; i<N; ++i){
        for(int j{0}; j<M; ++j){
            std::cout << dist[i][j] << ' ';
        }
        std::cout << '\n';
    }
}

void bfs(){
    while(!Q.empty()){
        auto curr = Q.front(); Q.pop();
        for(int k{0}; k<4; ++k){
            int nx = curr.x + dx[k];
            int ny = curr.y + dy[k];
            if(nx >= N || nx < 0 || ny >= M || ny < 0) continue;
            if(grid[nx][ny] != 0) continue;
            grid[nx][ny] = 1;
            dist[nx][ny] = dist[curr.x][curr.y] + 1;
            Q.push({nx, ny});
        }
    }
}

int main(){
    
    std::cin >> M >> N;

    for(int i{0}; i<N; ++i){
        for(int j{0}; j<M; ++j){
            std::cin >> grid[i][j];
        }
    }
    
    for(int i{0}; i<N; ++i){
        for(int j{0}; j<M; ++j){
            if(grid[i][j] == 1){
                Q.push({i, j});
            }
        }
    }

    bfs();
    //testprint();

    int max{0};
    
    for(int i{0}; i<N; ++i){
        for(int j{0}; j<M; ++j){
            if(grid[i][j] == 0){
                std::cout <<-1;
                return 0;
            }
            max = std::max(max, dist[i][j]);
        }
    }
    std::cout << max;
    

    return 0;
}