2589 - 보물섬

문제

코드

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

const int dy[4] = { -1, 0, 1, 0};
const int dx[4] = {0,1,0,-1};
int n,m, ret;
char a[54][54];
int visited[54][54];
vector<pair<int,int>> landList;

 
void solve(int y, int x){
		memset(visited, 0, sizeof(visited));
		visited[y][x] = 1;
		queue<pair<int,int>> q;
		q.push({y,x});
		while(q.size()){
			tie(y,x) = q.front(); q.pop();
			for(int i = 0; i < 4; i++){
				int ny = y +dy[i];
				int nx = x + dx[i];
				if(ny < 0 || ny >= n || nx < 0 || nx >=m || visited[ny][nx] || a[ny][nx] == 'W') continue;
				visited[ny][nx] = visited[y][x] + 1;
				q.push({ny, nx});
				ret = max(ret, visited[ny][nx]);
			}
		}
		return;
 }
 
int main(){
	cin >> n >> m;
	for(int i = 0; i<n; i++){
		for(int j = 0; j <m; j++){
			cin >> a[i][j];
			if(a[i][j] == 'L') landList.push_back({i,j});
		}
	}
	
	for(pair<int,int> a : landList){
		solve(a.first, a.second);
		
	}
	cout << ret -1 << '\n';
	
}

풀이

서로 가장 멀리 떨어진 곳이 보물섬이 있는 장소다.
구체적인 장소를 알려주지 않았으니 한 지점을 기준으로 가장 먼 곳이 몇인지 찾으면 된다.
BFS가 가장 적합하니 모든 경우를 BFS로 풀어주면 된다.

결과

후기

어렵지 않게 풀 수 있었다.
DFS가 구현하기 쉬워서 자주 쓰다보니 DFS로 가려고 낑낑대긴 했지만 BFS로 노선을 바꾸자마자 맞출수 있던 문제였다.