[C/C++] 백준 - 17086번 : 아기 상어2

https://www.acmicpc.net/problem/17086

17086번: 아기 상어 2

문제

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

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

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

---

BFS의 개념학습 문제이다.

아기상어가 존재하는 칸은 어처피 안전거리가 0이기 때문에 확인해줄 필요가 없다.

아기상어가 존재하지 않는 칸에서의 최소 안전거리를 모두 구한 후 최대값을 찾아주면 된다.

안전거리를 구하는 것은 BFS 알고리즘으로 쉽게 구할 수 있다. 나는 visited 2차원 배열을 통해 재방문을 방지하면서 시작했던 위치에서의 거리를 저장해주는 방식으로 진행하였다. 코드를 통해 확인하면 쉽게 이해할 수 있다.

#include <iostream>
#include <queue>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using namespace std; 

int N, M, sharkCnt;
int board[50 + 1][50 + 1];
int visited[50 + 1][50 + 1];
const int dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

void input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> board[i][j];
		}
	}
}

bool isValid(int y, int x) {
	return (1 <= y && y <= N && 1 <= x && x <= M);
}

int findMinDistance(int y, int x) {
	queue<pair<int, int>> q;
	memset(visited, 0, sizeof(visited));

	q.push({ y, x });
	visited[y][x] = 1;
	while (!q.empty()) {
		int curY = q.front().first;
		int curX = q.front().second;
		q.pop();

		for (int i = 0; i < 8; i++) {
			int ny = curY + dy[i];
			int nx = curX + dx[i];

			if (visited[ny][nx] != 0 || !isValid(ny, nx)) continue;
			if (board[ny][nx] == 1) return visited[curY][curX];
			visited[ny][nx] = visited[curY][curX] + 1;
			q.push({ ny, nx });
		}
	}
	return INF;
}

int solution() {
	int answer = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (board[i][j] == 1) continue;
			answer = max(answer, findMinDistance(i, j));
		}
	}
	return answer;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}