[백준] 17086 아기 상어 2

문제

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자. 

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

 

모든 빈 칸에서 BFS를 수행해서 가장 가까운 아기상어의 거리를 모두 구합니다.

그 거리중 가장 큰 값이 정답입니다.

브루트포스, BFS문제입니다.

 

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,-1,0,1,1,1,0,-1 }, dx[] = { 0,1,1,1,0,-1,-1,-1 }, INF = 987654321;

int N, M, mp[51][51], v[51][51], ans = 0;
int bfs(int Y, int X) {
	vi ans;
	v[Y][X] = 1;
	queue<pi>q;
	q.push({ Y,X });
	while (!q.empty()) {
		auto [y, x] = q.front();
		q.pop();
		rep(i, 8) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 1 && ny <= N && nx >= 1 && nx <= M && !v[ny][nx]) {
				v[ny][nx] = v[y][x] + 1;
				q.push({ ny,nx });
				if (mp[ny][nx] == 1) {
					ans.push_back(v[ny][nx] - 1);
				}
			}
		}
	}
	return *min_element(ans.begin(), ans.end());
}
int main() {
	FAST;
	cin >> N >> M;
	REP(i, N) {
		REP(j, M) {
			cin >> mp[i][j];
		}
	}
	REP(i, N) {
		REP(j, M) {
			if (mp[i][j]==0) {
				mset(v);
				ans = max(ans, bfs(i,j));
			}
		}
	}
	cout << ans;
}