BOJ : 2589 보물섬

입력

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

 

---

[BOJ 2589(G5) 리뷰]

L은 땅이고 W는 바다이다. 바다로는 이동할 수 없으며 땅으로만 다닐 수 있다.

각 육지사이의 거리가 최대가 될때 그 두개의 육지에는 보물이 묻혀있다고 한다.

이때 그 육지사이의 거리가 최대가 되는 거리가 몇인지 출력하면 된다.

 

완전탐색을 이용해 풀었다.

존재하는 모든 육지에대해서 BFS를 수행하여 가장 거리가 멀때를 기록하고 존재하는 모든 육지에대해 가장 큰 값이 최대값이 된다.

 

---

 

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
using namespace std;

#define X first
#define Y second
string board[52];
int vis[52][52];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	int n, m;
	cin >> n >> m;
	
	for (int i = 0; i < n; i++)
		cin >> board[i];


	int ans = 0;
	int InitCheck = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (InitCheck)
			{
				for (int k = 0; k < n; k++)
				{
					fill(vis[k], vis[k] + m, -1);
				}
				InitCheck = 0;
			}
			if (vis[i][j] != -1 || board[i][j] != 'L') continue;
			InitCheck = 1;
			queue <pair<int, int>> Q;
			vis[i][j] = 0;
			Q.push({ i,j });
			while (!Q.empty())
			{
				auto cur = Q.front(); Q.pop();
				for (int dir = 0; dir < 4; dir++)
				{
					int nx = cur.X + dx[dir];
					int ny = cur.Y + dy[dir];
					if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
					if (vis[nx][ny] != -1 || board[nx][ny] != 'L') continue;
					ans = max(ans, vis[cur.X][cur.Y] + 1);
					vis[nx][ny] = vis[cur.X][cur.Y] + 1;
					Q.push({ nx,ny });
				}
			}
		}
	}


	cout << ans;

	
}