[백준 2589] 보물섬

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

2589번: 보물섬

#include <cstdio>
#include <queue>
int N, M;
char map_char[50 + 2][50 + 2];

struct _st
{
	int x;
	int y;
	int cnt;
};
std::queue<_st> Q;
int visited[50 + 2][50 + 2];


void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%s", &map_char[i]);
	}
}

int BFS(int x, int y)
{
	static int dir_x[4] = { 0, 0 ,1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	Q = {};
	Q.push({ x, y, 0 });
	visited[x][y] = 1;

	_st data = {};
	while (!Q.empty()) {
		data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
			if (map_char[nx][ny] == 'W') continue;
			if (visited[nx][ny]) continue;
			visited[nx][ny] = 1;
			Q.push({ nx, ny, data.cnt + 1 });	// 어차피 가중치 똑같아서 체크 배열 필요 없다, 카운트 해주면 됨 
		}
	}
	return data.cnt;
}


int get_min()
{
	int max = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map_char[i][j] == 'W') continue;
			std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
			int tmp = BFS(i, j);
			max = (max > tmp) ? max : tmp;
		} 
	}
	return max;
}


int main()
{
	input();
	int ans = get_min();
	printf("%d", ans);
	return 0;
}

기억하자... 최단거리는 BFS다... 

 

 

// get_min( ) 함수

맵 전체를 한 번 훑으면서 육지(L)인지 바다(W) 인지 체크한다. 만약 바다이면 탐색을 하지 않고, 육지이면 " 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 두 육지"를 탐색하기 위해 BFS 함수를 호출한다. 

또한 이러한 두 육지 중 "가장 긴 시간이 걸리는" 곳을 선정해야 하기 때문에, 지역변수인 max와 BFS 함수의 탐색결과를 비교하여 더 큰 것을 선택해 준다. 

 

 

// BFS( ) 함수

육지 두 곳을 최단거리로 탐색해야 하기 때문에 BFS를 쓴다. 

이때, 첫 번째 육지와 두 번째 육지 사이의 거리를 저장하기 위해 구조체에 cnt 변수를 선언해 주었다. 어차피 한번 이동하는데 1시간이 걸리기 때문에 따로 cnt 비교용 chk 배열을 만들어줄 필요는 없다(이렇게 가중치가 모두 같은 경우는 cnt 변수로 해결해줄 수 있음). 그냥 가장 가까운 육지부터 먼 육지까지 걸린 시간이 각각의 cnt 변수에 저장될 것이다. 

가장 긴 시간이 걸리는 육지를 찾아야 하므로 가장 마지막으로 큐에 삽입된 구조체의 cnt 값을 리턴해준다. 

 

BFS 함수를 사용하면서 주의할 점은 반드시 방문 표시(이를 vistied배열로 구현)를 해주어야 한다는 점이다. 그래야 같은 곳을 중복 방문하면서 의도치 않게 이동 시간이 늘어나는 경우를 막을 수 있다.