백준 2589 c++ "보물섬" -[PlusUltraCode]

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

2589번: 보물섬

 

[필자 사고]

전형적인 BFS 탐색문제이다.

 

이 문제의 특이한 점은 모든 탐색 가능지점에서 가장 먼 부분을 찾아야 된다.

 

가로 세로 크기가 50 50 이 최대이므로 시간복잡도를 계산해 보겠다.

 

BFS 탐색 => 50*50 =2500;

 

각 육지마다 BFS탐색을 시도하면 50*50*(50*50) = 1억초 미만이므로 가능

 

전체 탐색을 진행해 줬다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;

int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
int N, M;
vector<vector<int>> Arr;


bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}
void Input() {
	cin >> N >> M;
	Arr.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(M);
	}
	string str;
	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int k = 0; k < M; k++) {
			if (str[k] == 'W') {
				Arr[i][k] = 1;
			}
			else {
				Arr[i][k] = 0;
			}
		}
	}
}

typedef pair<int, int> Node;
vector<vector<int>>  visited;
int Result = -1;
void BFS(int sero, int garo) {
	visited.clear();
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(M);
	}
	queue<Node> myQueue;
	myQueue.push({ sero,garo });
	visited[sero][garo] = 1;
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro) == false)continue;
			if (visited[nextSero][nextGaro] != 0)continue;
			if (Arr[nextSero][nextGaro] == 0) {
				visited[nextSero][nextGaro] = visited[nowSero][nowGaro] + 1;
				myQueue.push({ nextSero,nextGaro });
			}
		}
	}

	
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Result< visited[i][k]) {
				Result = visited[i][k];
			}
		}
	}
	
}

int main(void) {
	Input();
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (Arr[i][k] == 0) {
				BFS(i, k);
			}
		}
	}
	cout << Result-1;
}