[BOJ/Silver 2] 백준 17086 아기 상어 2(C++)

문제 링크

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

17086번: 아기 상어 2

문제

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

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

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

입력

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

출력

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

예제 입력 1

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

예제 출력 1

2

예제 입력 2

7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1

예제 출력 2

2

알고리즘 분류

• 그래프 탐색
• 브루트포스 알고리즘

풀이

값이 0인 칸마다 한 번씩 BFS를 실행하여 1과의 거리의 최댓값을 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 55
#define LL long long
#define INF 2e9

using namespace std;
int N, M;
int MAP[MAX][MAX];
bool visited[MAX][MAX];
int moveY[8] = { -1,-1,0,1,1,1,0,-1 };
int moveX[8] = { 0,1,1,1,0,-1,-1,-1 };
int answer = 0;

void init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = false;
		}
	}
}

int BFS(int Y, int X) {
	init();
	queue<pair<pair<int, int>, int> > Q;
	int Cnt = 0;
	visited[Y][X] = true;
	Q.push(make_pair(make_pair(Y, X), Cnt));

	while (!Q.empty()) {
		int CurY = Q.front().first.first;
		int CurX = Q.front().first.second;
		int CurCnt = Q.front().second;
		Q.pop();

		if (MAP[CurY][CurX] == 1) {
			return CurCnt;
		}
		for (int i = 0; i < 8; i++) {
			int nextY = CurY + moveY[i];
			int nextX = CurX + moveX[i];
			if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < M) && (!visited[nextY][nextX])) {
				visited[nextY][nextX] = true;
				Q.push(make_pair(make_pair(nextY, nextX), CurCnt + 1));
			}
		}
	};

	return 0;
}

int main() {
	FIRST
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> MAP[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (MAP[i][j] == 0) {
				answer = max(answer, BFS(i, j));
			}
		}
	}
	cout << answer << "\n";

	return 0;
}