[백준/C++] 2589. 보물섬

문제

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

육지와 바다로 이루어진 nxm 맵에서 

육지에서 시작해서, 바다를 거치지 않고 갈 수 있는 가장 먼 육지까지의 최단경로를 구하는 문제이다. 

풀이

BFS를 이용해서 풀었다! 또한, 모든 육지가 시작점이 될 수 있기 때문에 완전탐색이기도 하다. 

모든 육지에서 BFS를 돌려서, 다른 육지까지의 최단경로를 모두 구해서 그 중에 최댓값을 출력했다.

코드

#include <iostream>
#include <queue>

using namespace std;

int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int map[52][52] = { 0, };
int cache[52][52] = { 0, };
int max_dist = 0;

void BFS(int r, int c) {
	queue<pair<int, int>> q;
	q.push(make_pair(r, c));
	
	cache[r][c] = 1;
	while (!q.empty()) {
		int temp_r = q.front().first;
		int temp_c = q.front().second;
		q.pop();

		max_dist = max(max_dist, cache[temp_r][temp_c]);
		for (int i = 0;i < 4;i++) {
			int next_r = temp_r + dr[i];
			int next_c = temp_c + dc[i];
			if (map[next_r][next_c] == 1 && cache[next_r][next_c] == 0) {
				q.push(make_pair(next_r, next_c));
				cache[next_r][next_c] = cache[temp_r][temp_c] + 1;
			}
		}
	}
}
int main(void) {
	int R, C;
	cin >> R >> C;
	for (int r = 1;r <= R;r++) {
		for (int c = 1;c <= C;c++) {
			char temp;
			cin >> temp;
			if (temp == 'W') map[r][c] = 0;
			else map[r][c] = 1;
		}
	}
	for (int r = 1;r <= R;r++) {
		for (int c = 1;c < C;c++) {
			if (map[r][c] == 1) { ////
				fill(&cache[0][0], &cache[51][52], 0); /////
				BFS(r, c);
			}
			
		}
	}
	cout << max_dist -1 << endl;
}

결과