백준 2589, 보물섬

 

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

2589번: 보물섬

요약

 

 

바다와 육지로 이루어진 지도에서, 육지에서 육지로 이동하는 최대 최단거리를 구한다.

---

1. 육지에서 인접한 육지로 이동하는 비용이 1이므로, 모든 가중치가 동일한 무방향 가중치 그래프를 떠올릴 수 있다.

 

2. 모든 가중치가 동일하고, 최단거리를 구해야 하므로 BFS(너비 우선 탐색) 기법으로 최단거리를 구할 수 있다.

 

3. 최단거리의 최대 값을 구하기 위해 지도 상의 Brute Force 기법을 사용하여 모든 육지에서 출발하였을 때의 최단거리의 최대값을 구하였다.

 

4. 최대 육지의 개수는 2500개이고, BFS에서 최대 2500개의 육지를 탐색하므로, 시간제한 안에 모든 연산이 수행 가능하다.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<pair<int, int>, int> piii;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

int N, M, ans;
int arr[51][51];
int mark[51][51];
queue <piii> q;

void BFS();
void check();

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < M; j++) {
			if (s[j] == 'W') arr[i][j] = 1;
			else arr[i][j] = 0;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] == 0) {
				memset(mark, 0, sizeof(mark));
				q.push({ {j,i},1 });
				while (q.size()) BFS();
				check();
			}
		}
	}
	cout << ans;
	return 0;
}

void BFS() {
	piii f = q.front();
	q.pop();
	int x = f.first.first;
	int y = f.first.second;
	int d = f.second;
	if (x < 0 || x > M - 1 || y < 0 || y > N - 1) return;
	if (arr[y][x] == 1) return;
	if (mark[y][x] != 0) return;
	mark[y][x] = d;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		q.push({ {nx,ny},d + 1 });
	}
}

void check() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) ans = max(ans, mark[i][j] - 1);
	}
}