BOJ 백준 2589 보물섬 <BFS>

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

< 보물섬 >

 이 문제는 바다와 육지가 주어지고 육지에 보물 두 개를 두었을 때 보물 두 개의 거리가 가장 멀게 배치하고 그 거리를 구해주는 문제이다.

두 보물을 배치한다곤 했지만 보물을 고려하지 않고, 두 육지의 거리가 가장 긴 경우를 출력해주기만 하면 된다.

배열을 for문으로 돌아가면서 'L', 즉 육지마다 BFS알고리즘을 이용하여 최대 거리들을 계산해주면 된다.

#include <iostream>
#include <memory.h>
#include <queue>

#define SIZE 51

using namespace std;

int xarr[4] = { 1,-1,0,0 };
int yarr[4] = { 0,0,1,-1 };

int n, m;
char map[SIZE][SIZE];
int iMax = 0;

bool InMap(int x, int y)
{
	return (0 <= x && x < n && 0 <= y && y < m);
}

void bfs(int x, int y)
{
	int path = 0;

	bool visit[SIZE][SIZE];
	memset(visit, 0, sizeof(visit));

	queue< pair<int, int> > q;
	q.push({ x, y });
	visit[x][y] = true;

	while (!q.empty())
	{
		int qsize = q.size();
		for (int i = 0; i < qsize; ++i)
		{
			int cur_x = q.front().first;
			int cur_y = q.front().second;
			q.pop();

			for (int j = 0; j < 4; ++j)
			{
				int next_x = cur_x + xarr[j];
				int next_y = cur_y + yarr[j];

				if (!InMap(next_x, next_y)) continue;
				if (map[next_x][next_y] == 'W') continue;
				if (visit[next_x][next_y]) continue;

				q.push({ next_x, next_y });
				visit[next_x][next_y] = true;
			}
		}
		++path;
	}
	if (iMax < path - 1) iMax = path - 1;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		cin >> map[i];
	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (map[i][j] == 'L')
			{
				bfs(i, j);
			}
		}
	}

	cout << iMax << '\n';

	return 0;
}