[백준] 2589번 보물섬

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

2589번: 보물섬

최단경로를 구하는 것이기 때문에 BFS(너비 우선 탐색)로 풀면 된다. 가중치가 없는 그래프에서 최단경로를 구하라고 하면 무조건 BFS이다. 이 지도에서는 상하좌우 어디든 비용이 1이므로 가중치가 없다고 할 수 있다.

일단 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;


int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<char>> map(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	int maxDistance = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 'L') {
				queue<tuple<int, int, int>> q;
				vector<vector<bool>> visited(n, vector<bool>(m));
				q.push(make_tuple(i, j, 0));
				while (!q.empty()) {
					tuple<int, int, int> cur = q.front();
					q.pop();
					int row = get<0>(cur);
					int col = get<1>(cur);
					if (!visited[row][col]) {
						if (get<2>(cur) > maxDistance)
							maxDistance = get<2>(cur);
						visited[row][col] = true;
						if (row + 1 < n && map[row + 1][col] == 'L' && !visited[row + 1][col]) {
							q.push(make_tuple(row + 1, col, get<2>(cur) + 1));
						}
						if (row - 1 >= 0 && map[row - 1][col] == 'L' && !visited[row - 1][col]) {
							q.push(make_tuple(row - 1, col, get<2>(cur) + 1));
						}
						if (col + 1 < m && map[row][col + 1] == 'L' && !visited[row][col + 1]) {
							q.push(make_tuple(row, col + 1, get<2>(cur) + 1));
						}
						if (col - 1 >= 0 && map[row][col - 1] == 'L' && !visited[row][col - 1]) {
							q.push(make_tuple(row, col - 1, get<2>(cur) + 1));
						}
					}
				}
			}
		}
	}
	cout << maxDistance;
	return 0;
}

육지인 칸이라면 매 칸마다 BFS를 하면 된다. BFS를 하기 위해 큐를 사용했고 큐에는 tuple 객체를 만들어 넣어주었다.

튜플의 첫 번째 원소는 행, 두 번째 원소는 열, 세 번째 원소에는 BFS를 시작한 그 칸에서 여기까지의 거리를 저장해주었다. 그리고 최대 거리를 maxDistance에 저장하며 갱신해주었다.

상하좌우를 탐색하기만 하면 된다. 다른 BFS와 조금 다른 점은 보통 BFS는 특정 지점에서 특정 지점으로 가는 최단경로를 구하는 것이기 때문에 visited 배열도 하나만 필요했고 다 공유했다. 하지만 이 문제에서는 특정 지점에서 특정 지점으로 가는 것이 아니라 어느 지점인지 모르는 지점에서 어느 지점인지 모르는 지점까지의 최단경로 중 최장경로를 찾는 것이기 때문에 모든 육지에서 나머지 육지로 가는 모든 경우의 수를 구해야 한다. 따라서 한 칸마다 BFS를 새로 시작하기 때문에 매 칸마다 그 칸을 위한 visited 배열도 새로 만들고 queue도 새로 만들어줘야 한다.