[백준/BOJ] 백준 2589번 : 보물섬

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

2589번: 보물섬

각각의 육지 위치해서 갈 수 있는 가장 먼 육지까지 거리 중 최댓값을 구한다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <queue>
#include <string>
using namespace std;

int n, m;
vector<string> board;
vector<pair<int, int>> land;
int discovered[50][50];
int depth[50][50];
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//start지점에서 갈 수 있는 가장 먼 육지까지의 거리를 구한다
int Solve(pair<int, int> start)
{
	memset(discovered, 0, sizeof(discovered));
	memset(depth, 0, sizeof(depth));

	discovered[start.first][start.second] = 1;
	depth[start.first][start.second] = 0;

	int ret = -1;

	queue<pair<int, int>> q;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//갈수 있는 가장 먼 육지까지의 거리를 구한다
		if (board[here.first][here.second] == 'L')
		{
			ret = max(ret, depth[here.first][here.second]);
		}

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);

			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && board[there.first][there.second] == 'L' && discovered[there.first][there.second] == 0)
			{
				discovered[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;

				q.push(there);
			}
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string temp;
	int result = -1;

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		for (int j = 0; j < m; j++)
		{
			//육지들의 정보를 저장한다
			if (temp[j] == 'L')
				land.push_back(make_pair(i, j));
		}
		board.push_back(temp);
	}

	for (int i = 0; i < land.size(); i++)
	{
		//각각의 육지 위치해서 갈 수 있는 가장 먼 육지까지 거리중 최대값을 구한다
		result = max(result, Solve(land[i]));
	}

	cout << result;

	return 0;
}