백준 보물섬

이번 문제는 BFS다.

 

두 곳 사이를 최단 거리로 이동하면서 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다고 한다.

 

근데 보물이 어디있는지는 없고 그냥 어떤 육지 지점에서 시작해서 그 근방의 모든 갈 수 있는 육지에 대해 최단 거기를 구하고 그 거리가 가장 최대일때를 구하면 된다.

 

그래서 입력받은 맵을 돌며 육지가 있을때마다 bfs를 실시했고 그때마다 최대값을 비교해서 갱신해줬다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
vector<string> maps;
int tmp[10][10];
int cnt;
int n, m;
int dp[51][51];
bool visited[51][51];

int main() {
	cin >> n >> m;
	string s;
	
	for (int i = 0; i < n; i++) {
		cin >> s;
		maps.push_back(s);
	}
	
	int res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (maps[i][j] == 'L') {
				int ans = 0;
				fill_n(&visited[0][0], 51 * 51, false);
				queue<tuple<int, int, int>> q;
				q.push({ i, j, ans});
				visited[i][j] = true;
				while (!q.empty()) {
					auto it = q.front();
					int x = get<0>(it);
					int y = get<1>(it);
					int dist = get<2>(it);

					q.pop();

					res = max(res, dist);
					
					for (int d = 0; d < 4; d++) {
						int nx = x + dx[d];
						int ny = y + dy[d];

						if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
							if (!visited[nx][ny] && maps[nx][ny] != 'W') {
								visited[nx][ny] = true;
								q.push({ nx,ny, dist+1 });
							}
						}
					}
				}
			}
		}
	}
	

	cout << res << endl;
	return 0;
}