[BOJ 7576] 토마토

백준 :: BOJ :: 7576 :: 토마토

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

#include <bits/stdc++.h>

using namespace std;

struct a {

int i, j;

};

int N, M, ans, result;

int arr[1000][1000];

int di[] = { 0,0,1,-1 }, dj[] = {1,-1,0,0};

bool visited[1000][1000];

queue<a> q;

inline bool check(int i, int j) { return (i >= 0 && j >= 0 && i < N && j < M) ? true : false; }

int bfs() {

if (ans == 0) return  0;

while (!q.empty()) {

int t = q.size();

while (t--) {

auto tmp = q.front(); q.pop();

for (int d = 0; d < 4; d++) {

int ni = tmp.i + di[d], nj = tmp.j + dj[d];

if (check(ni, nj) && arr[ni][nj]==0 && !visited[ni][nj]) {

visited[ni][nj] = 1; ans--; q.push({ ni,nj });

}

}

}

result++;

if (ans == 0) return result;

}

return -1;

}

int main() {

std::ios::sync_with_stdio(false); cin.tie(0);

cin >> M >> N; ans = 0; result = 0;

for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {

cin >> arr[i][j]; 

if (arr[i][j]==1) {

q.push({ i,j }); visited[i][j] = 1;

}

else if (arr[i][j] == 0) ans++;

}

cout << bfs();

return 0;

}