백준 2589번 보물섬 C++

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

 

BST 탐색으로 해결할 수 있는 문제이다.

지도의 모든 부분을 검사하면서 만약 L인 지역이면 그곳부터 BST탐색을 시작하고, 가장 먼 곳 까지의 거리를 구하고 구한 거리들 중 가장 큰 값을 찾으면 해결할 수 있다.

 

땅을 방문했는지 안했는지 검사하는 visited 벡터를 만들었고, 새로 검사를 시작할 때는 visited 벡터를 초기화 해주었다.

그리고 BST탐색을 하기 위한 큐에는 pair<pair<int, int>, int>을 사용해서 안쪽에 있는 pair는 좌표 정보를, int는 거리 정보를 저장하면서 탐색을 하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int r, c;
queue < pair<pair<int, int>, int>> q;

void Init_visited(vector<vector<bool>> &visited) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			visited[i][j] = false;
		}
	}
}

int BST(const vector<vector<char>> &v, vector<vector<bool>> &visited, int row, int col, int cnt) {
	int dist = 0;
	q.push({ {row,col},cnt });
	while (!q.empty()) {
		auto a = q.front();
		q.pop();
		int currRow = a.first.first;
		int currCol = a.first.second;
		int currCnt = a.second;
		dist = max(dist, currCnt);
		if (currRow - 1 >= 0 && !visited[currRow - 1][currCol] && v[currRow - 1][currCol]=='L') {
			visited[currRow - 1][currCol] = true;
			q.push({ {currRow - 1,currCol},currCnt + 1 });
		}
		if (currRow + 1 < r && !visited[currRow + 1][currCol] && v[currRow + 1][currCol] == 'L') {
			visited[currRow + 1][currCol] = true;
			q.push({ {currRow + 1,currCol},currCnt + 1 });
		}
		if (currCol - 1 >= 0 && !visited[currRow][currCol - 1] && v[currRow][currCol - 1] == 'L') {
			visited[currRow][currCol - 1] = true;
			q.push({ {currRow,currCol - 1},currCnt + 1 });
		}
		if (currCol + 1 < c && !visited[currRow][currCol + 1] && v[currRow][currCol + 1] == 'L') {
			visited[currRow][currCol + 1] = true;
			q.push({ {currRow,currCol + 1},currCnt + 1 });
		}
	}
	return dist;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> r >> c;
	string str;
	vector<vector<char>> v(r, vector<char>(c));
	vector<vector<bool>> visited(r, vector<bool>(c, false));
	for (int i = 0; i < r; i++) {
		cin >> str;
		for (int j = 0; j < str.length(); j++) {
			v[i][j] = str[j];
		}
	}
	int ans = -1;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (v[i][j] == 'L') {
				Init_visited(visited);
				visited[i][j] = true;
				int dist = BST(v, visited, i, j, 0);
				ans = max(ans, dist);
			}
		}
	}
	cout << ans;
};