[C++] 백준 7576번: 토마토

 

bfs도 어느정도 적응이 되어가는 것 같다.

 

앞서 풀었던 미로 탐색 문제랑 비슷했는데, 토마토는 여러곳에서 bfs를 시작하게 될 수 있다는 것에 차이가 있었다.

고민하다가 토마토가 있는 지점 모두를 큐에 먼저 넣어놓고 bfs를 시작했고, board가 0인지점을 dist -1로 초기화했다. 만약 dist가 -1이 남아있는 지점이 있으면 도달할 수 없는 곳이 있는 것으로 판단하고, -1을 출력해서 마무리했다.

 

이전에 봤던 max함수를 써먹었고, dist도 잘 써먹었다.

 

#include <iostream>
#include <queue>
#define X first
#define Y second
using namespace std;

int n, m;
int board[1005][1005];
int dist[1005][1005];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
queue <pair<int, int>> Q;

int main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);
   cin >> m >> n;
   for(int i = 0; i < n; i++){
       for(int j = 0; j < m; j++){
           cin >> board[i][j];
           if(board[i][j] == 1){
                Q.push({i, j});
           }
           if(board[i][j] == 0){
               dist[i][j] = -1;
           } 
       }
   }
   while(!Q.empty()){
       auto cur = Q.front(); Q.pop();
       for(int i = 0; i < 4; i++){
           int nx = cur.X + dx[i];
           int ny = cur.Y + dy[i];
           if(nx >= n || nx < 0 || ny >= m || ny < 0) continue;
           if(dist[nx][ny] >= 0) continue;
           Q.push({nx, ny});
           dist[nx][ny] = dist[cur.X][cur.Y] + 1;
           
       }
   }
   int ans = 0;
   for(int i = 0; i < n; i++){
       for(int j = 0; j < m; j++){
            if(dist[i][j] == -1) {
                cout << -1;
                return 0;
            }
            ans = max(ans, dist[i][j]);
       }
   } 
   
   cout << ans;
   return 0;
}