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

백준 2589

🌲 문제 요약

보물이 서로 간의 최단 거리로 이동하는 데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다고 할 때, 보물 사이 이동 시간을 구하는 문제.

🌲 문제 풀이

보물섬 지도의 정보를 배열 a에 저장한 후, a를 순회하며 a[i][j]의 값이 'L'일 때마다 bfs 함수를 호출한다.
bfs 함수는 보물 사이를 최단 거리로 이동하는 데 걸리는 시간을 구하여 이를 ret과 비교한 뒤, 더 큰 값을 ret에 저장하는 역할을 한다.

🌲 주의

배열 a의 자료형이 int가 아닌 char임에 유의한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, visited[55][55], ret = -1;
char a[55][55];
queue<pair<int, int>> q;

void bfs(int y, int x) {
	visited[y][x] = 1;
	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) continue;
			if (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] - 1);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 'L') {
				memset(visited, 0, sizeof(visited));
				bfs(i, j);
			}
		}
	}
	cout << ret << '\n';
	
	return 0;
}