[백준][2589][c++] 보물섬

보물섬 문제 링크

[문제 풀이]
가로 세로가 50이하이기 때문에 모든 통행 가능한 물 좌표끼리의 거리를 BFS를 구하는 것이 가능하다.

[코드]

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#define N_MAX 51

using namespace std;

int L, W;
int map[N_MAX][N_MAX];
vector<vector<pair<int, int>>> territory;
int dir_y[4] = { 0,0,1,-1 };
int dir_x[4] = { 1,-1,0,0 };


int BFS(int y, int x) {
	queue<pair<int, int>> q;
	bool visited[N_MAX][N_MAX] = { false, };
	int distance[N_MAX][N_MAX] = { 0, };
	q.push(make_pair(y, x));
	visited[y][x] = true;
	int result = -1;

	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int new_y = cur.first + dir_y[dir];
			int new_x = cur.second + dir_x[dir];
			if (new_y < 0 || new_y >= L || new_x < 0 || new_x >= W) continue;
			if (visited[new_y][new_x] || map[new_y][new_x] == 'W') continue;
			distance[new_y][new_x] = distance[cur.first][cur.second] + 1;
			visited[new_y][new_x] = true;
			q.push(make_pair(new_y, new_x));
			//최단 거리가 가장 큰 값을 찾는 것
			if (result < distance[new_y][new_x]) result = distance[new_y][new_x];
		}
	}
	return result;
}


int solve() {
	int result = -1;
	for (int y = 0; y < L; y++) {
		for (int x = 0; x < W; x++) {
			if (map[y][x] == 'L') {
				//물이면 BFS를 통해 최단 거리가 가장 큰 것을 얻은 후 전체에서 가장 큰 것인지 얻는다
				result = max(result, BFS(y, x));
			}
		}
	}
	return result;
}


int main() {
	cin >> L >> W;
	string line;
	for (int y = 0; y < L; y++) {
		cin >> line;
		for (int x = 0; x < W; x++) {
			map[y][x] = line[x];
		}
	}
	int ans = solve();
	cout << ans << "\n";
}

[총평]
처음에는 물로 이루어진 구역들을 BFS를 통해 찾아서 vector에 넣은 다음에 조합을 통해 두 개를 골라서 BFS를 통해 최대 최단 거리를 구하고자 했는데, 이 조합 하는 과정이 많은 computation 이 걸리는 것 같다.