[백준 2589] 보물섬(BFS)

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

풀이

1.육지인 좌표에서 bfs를 돌리고

2. 그 좌표에서 bfs를 돌렸을 때 최단거리를 구함

3. 모든 육지좌표에서 1,2를 수행하며 최단거리 갱신

4. 마지막에 구한 최단거리==정답

핵심: 어떤 육지좌표에서 1,2를 수행하고 다른 육지좌표에서 최단거리를 구할 때 check배열은 0으로 초기화(방문하지않았다고)해야합니다.

그리고 정답을 출력할 때, 최단거리에서 1을 빼준값을 출력해야합니다. 아래 그림을 참조하면됩니다.

당연하지만, bfs가 아래 그림처럼 최단거리로 갱신해주기 때문에  최단거리문제에서 dfs보다 bfs가 훨씬유리합니다.

코드

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
char map[50][50];
int check[50][50];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n, m;
int cnt;
int max_value = 0;
void bfs(int y, int x);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> map[i];
	
	//육지일때 그 좌표에서 최단거리구해봄
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 'L')
				//육지에서시작되는 각 좌표들로부터의 최단거리를
			{
				bfs(i, j);
				max_value = max(max_value, cnt);
				cnt = 0;
			}
		}
	}
	//육지에서 bfs를돌리면 그 육지의 좌표의 인접한 좌표가2가되므로 하나빼줘야됨
	cout << max_value-1 << '\n';
}
void bfs(int y, int x)
{
	//핵심! 육지인 모든곳을 탐색하므로 한번 탐색할때마다 갱신
	memset(check, 0, sizeof(check));
	queue<pair<int, int>>q;
	q.push({ y,x });
	check[y][x] = 1;
	while (!q.empty())
	{
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			//좌표범위내에서 확인
			if (nx >= 0 && ny >= 0 && nx < m && ny < n)
			{
				//만약 육지이고, 만나지않았떤길이면
				if (map[ny][nx] == 'L' && check[ny][nx] == 0)
				{
					check[ny][nx] = check[y][x] + 1;
					cnt = max(cnt, check[ny][nx]);
					q.push({ ny,nx });
				}
				
			}
		}
	}
}

결과