[baekjoon 2589] 보물섬 (BFS, 브루트포스) (C++)

www.acmicpc.net/problem/2589

2589번: 보물섬

문제의 조건은

"보물은 서로 간에 최단 거리로 이동하는 데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다."이다.

 

즉, 보물의 위치가 정해져 있지 않고, 탐색할 수 있는 육지 중에서 최단 거리 중 가장 긴 시간이 걸리는 곳을 찾으면 된다.

 

처음에 문제를 보고, 위치가 없는데 어떻게 탐색을 할까? 생각을 했는데 입력 사이즈가 50 x 50 인 것을 확인하고 브루트 포스로 전부 탐색해버리면 되겠다는 생각이 들었다.

 

또한 최단거리를 구해야 하므로 BFS를 이용해서 거리를 기록해주었다.

 

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

int n, m, arr[51][51], check[51][51], mx, temp, xmove[4] = { 1, -1, 0, 0 }, ymove[4] = { 0, 0, 1, -1 };
int record[51][51];
string s;
vector<pair<int, int>> v;

void BFS(int startx, int starty) {
	queue<pair<int, int>> q;
	check[startx][starty] = true;
	q.push(make_pair(startx, starty));
	temp = 0;

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

		for (int i = 0; i < 4; i++) {
			int nx = x + xmove[i];
			int ny = y + ymove[i];

			if (arr[nx][ny] == 1 && !check[nx][ny]) {
				if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
					q.push(make_pair(nx, ny));
					check[nx][ny] = true;
					record[nx][ny] = record[x][y] + 1;
					temp = max(temp, record[nx][ny]);
				}
			}
		}
	}


}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < m; j++) {
			if (s[j] == 'L') {
				arr[i][j] = 1;
				v.push_back(make_pair(i, j));
			}
		}
	}

	for (int i = 0; i < v.size(); i++) {
		BFS(v[i].first, v[i].second);
		mx = max(temp, mx);
		for (int k = 0; k < n; k++) {
			for (int j = 0; j < m; j++) {
				check[k][j] = false;
				record[k][j] = 0;
			}
		}
	}

	cout << mx;

}

탐색을 줄여보고자 탐색이 가능한 육지일 경우 벡터에 저장해서 그 좌표값만 BFS를 진행시켜주었다.

(매번 탐색 배열을 초기화해주어야 정상적으로 탐색이 이루어진다.)