BOJ 2589 - 보물섬

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	19410	6691	4842	38.456%

문제

---

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력

---

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

출력

---

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

접근

---

L이 붙어있는 하나의 대륙을 그룹으로 묶어서 BFS를 진행하면
가장 먼 끝점들이 어떤 점인지 알기가 굉장히 힘들다.
너무 많은 생각을 하지 않는 것이 이 문제의 핵심이다.

모든 점에서 BFS를 진행해도, 시간복잡도가 2500 * 2500으로 널널하다.
순회하면서 모든 점에서 제일 멀리 떨어진 점을 찾으면 된다.

풀이

---

기본 BFS 코드이다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int N, M, ans = 0;
char arr[50][50];
bool visited[50][50];


void BFS(int i, int j)
{
	queue<pair<pair<int, int>, int>> q;
	MS(visited, false);
	q.push({ { i, j }, 0 });
	visited[i][j] = true;
	while (!q.empty())
	{
		int y = q.front().first.first;
		int x = q.front().first.second;
		int dist = q.front().second;
		q.pop();
		ans = max(ans, dist);
		FUP(d, 0, 3)
		{
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M || visited[ny][nx] || arr[ny][nx] == 'W') continue;
			visited[ny][nx] = true;
			q.push({ {ny, nx}, dist + 1 });
		}
	}

}

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

	CIN2(N, M);
	FUP(i, 0, N - 1)
	{
		FUP(j, 0, M - 1)
		{
			CIN(arr[i][j]);
		}
	}
	FUP(i, 0, N - 1)
	{
		FUP(j, 0, M - 1)
		{
			if (arr[i][j] == 'L')
			{
				BFS(i, j);
			}
		}
	}
	COUT(ans);

	return 0;
}