[C++] 백준/Gold/2589. 보물섬

문제: 보물섬(백준 2589번)

문제 분석

지도 상에 있는 땅('L')과 물('W')이 주어질 때, 모든 땅에서 출발하여 가장 멀리 떨어진 땅까지의 최단 거리를 구하는 문제다. 즉, 모든 땅을 시작점으로 BFS를 수행하여 최대 이동 거리를 계산한 후 그 중 가장 큰 값을 출력하면 된다.

---

문제의 핵심은 다음과 같다.

BFS를 사용해 각 땅에서의 최대 거리를 계산

• 맵 상에서 땅('L')에서 시작해 상하좌우로 이동하며, 각 칸까지 도달하는 최소 이동 횟수를 구한다.

모든 땅을 시작점으로 탐색

• 물('W')는 탐색 대상이 아니므로 건너뛴다.
• 최대 이동 횟수를 찾는다.

BFS

역할:

주어진 시작점에서 BFS를 수행하여, 도달할 수 있는 모든 땅까지의 최단 거리를 계산하고, 그 중 최대 거리를 반환한다.

동작:

• depth 배열을 통해 각 칸까지의 이동 횟수를 기록한다.
• 상하좌우 이동하면서, 범위를 벗어나지 않고 땅('L')일 경우만 탐색한다.
• BFS 과정 중 최댓값을 업데이트하여 result에 저장한다.

전체 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<string> board;
int offset[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

int BFS(pair<int, int> start) {
	int result = 0;
	vector<vector<int>> depth(n, vector<int>(m, -1));
	queue<pair<int, int>> bfs;
	bfs.push(start);
	depth[start.first][start.second] = 0;
	while (!bfs.empty()) {
		int x, y; tie(y, x) = bfs.front();
		bfs.pop();

		if (result < depth[y][x]) {
			result = depth[y][x];
		}

		for (int i = 0; i < 4; i++) {
			int xx = x + offset[i][0];
			int yy = y + offset[i][1];
			if (xx < 0 || xx >= m || yy < 0 || yy >= n)continue;
			if (depth[yy][xx] == -1 && board[yy][xx] == 'L') {
				bfs.push({ yy, xx });
				depth[yy][xx] = depth[y][x] + 1;
			}
		}
	}
	return result;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	board.resize(n);
	
	for (int i = 0; i < n; i++) {
		cin >> board[i];
	}
	int answer = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 'W')continue;
			int result = BFS({ i, j });
			answer = max(answer, result);
		}
	}
	cout << answer;
}