[백준 7576번] 토마토

문제 링크:https://www.acmicpc.net/problem/7576

7576번: 토마토

 

<문제 풀이> BFS

이문제는 기본적인 bfs를 사용해서 최단거리를 구하면 됩니다.

 

그런데 익은 토마토가 여러 개이면 모든 익은 토마토에 대해서 동시에 출발을 해야 됩니다.

 

시작점을 여러개 두고 bfs를 동시에 진행하는 방법은

시작점을 모두 queue에 넣고 시작하면 됩니다. (그러면 번갈아가면서 push, pop을 하기 때문에 동시에 출발시킨 효과)

 

 

<C++ 소스 코드>

#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
using namespace std;
 
#define X first
#define Y second
 
int box[1000][1000];
int visited[1000][1000];
int dx[4] = {1 ,0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int n, m;
 
 
void bfs() {
    queue<pair<int, int> > Q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (box[i][j] == 1) {
                Q.push({ i,j });
            }
            if (box[i][j] == 0) {
                visited[i][j] = -1;
            }
        }
    }
    
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny <0 || nx>=n || ny >=m) continue;
            if (visited[nx][ny] >= 0) continue;
            Q.push({ nx, ny });
            visited[nx][ny] = visited[cur.X][cur.Y] + 1;
        }
    }
    
}
 
int cal_res() {
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visited[i][j] == -1) return -1;
            res = max(res, visited[i][j]);
        }
    }
    return res;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> box[i][j];
        }
    }
    bfs();
   
    cout << cal_res();
    return 0;
}