백준 [2589] 보물섬

출처 : https://www.acmicpc.net/problem/2589

2589번: 보물섬

 

	#include<iostream>
	#include<queue>
	#include<algorithm>
	#include<cstring>
	using namespace std;
	char map[51][51];
	bool visited[51][51];
	queue<pair<pair<int, int>, int>> q;
	int dx[4] = { -1,0,0,1 };
	int dy[4] = { 0,1,-1,0 };
	int N, M, ans = 0;
	void bfs(int x, int y) {
	visited[x][y] = true;
	q.push({ { x, y }, 0 });
	while (!q.empty()) {
	x = q.front().first.first;
	y = q.front().first.second;
	int t = q.front().second;
	q.pop();
	for (int i = 0; i < 4; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	if (map[nx][ny] == 'W') continue;
	if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny]) {
	visited[nx][ny] = true;
	q.push({ {nx, ny},t + 1 });
	ans = max(ans, t + 1);
	}
	}
	}
	}
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	cin >> map[i][j];
	}
	}
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	if (map[i][j] == 'L') {
	memset(visited, false, sizeof(visited));
	bfs(i, j);
	}
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw 2589.cpp hosted with ❤ by GitHub

bfs

" 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. "

이 말이 무슨말인가 싶었는데, 결국 bfs를 통해서 거리를 탐색했을 때 가장 먼 지점까지의 이동 시간을 구하면 되는 것이었다.

출발지점이 정해지지 않았으므로, 완전탐색 + bfs 를 사용해야한다.

방문여부를 체크해주며 queue에 x,y 좌표와 각 지점까지의 소요시간을 넣어주어 max값을 계산해주었다.

또한 각 좌표에서 출발할 때마다 visited 배열을 초기화해주는 작업이 필요하다

memset -> cstring

max -> algorithm