[BOJ] 2589번_보물섬_BFS (C++)

[문제]

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

보물섬 지도를 통해 보물을 찾고 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 문제이다. 보물섬 지도는 L과 W로 표시되어있다. 지도상으로 L로 표시된 곳만 이동 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다.

[사용 알고리즘]

BFS(너비 우선 탐색)

[풀이 핵심]

• 보물 지도의 최대 크기가 50*50이므로 완전 탐색을 해도 시간초과가 나지않는다. 이점을 이용해서 BFS를 돌며 보물 지도의 모든 L위치에서의 최단 거리를 구하고, 그 중 최대값을 result에 저장해가며 답을 구했다.

[코드]

//boj2589번_보물섬_그래프

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

char graph[51][51];
bool visited[51][51];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int N, M;

int result = 0;

void BFS(int x, int y) {
	visited[x][y] = true;

	queue<pair<pair<int, int>, int>> q;
	q.push({ { x,y },0 });

	while (!q.empty()) {
		x = q.front().first.first;
		y = q.front().first.second;

		int count = q.front().second;

		q.pop();

		result = max(result, count);

		for (int i = 0; i < 4; i++) {
			int next_x = x + dx[i];
			int next_y = y + dy[i];

			if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && graph[next_x][next_y] == 'L' && !visited[next_x][next_y]) {
				visited[next_x][next_y] = true;
				q.push({ { next_x,next_y }, count + 1 });
			}
		}
	}
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> graph[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (graph[i][j] == 'L') {
				for (int a = 0; a < N; a++) {
					for (int b = 0; b < M; b++) {
						visited[a][b] = false;
					}
				}
				BFS(i, j);
			}
		}
	}
	cout << result;

	return 0;
}