BaekJoon 2589번: 보물섬(C++)

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

2589번: 보물섬

풀이법

1) 방문한 곳을 체크하는 visited배열과 BFS기반의 알고리즘으로 문제를 해결했다.

2) BFS알고리즘을 기준으로, x,y,count 변수를 각각의 queue에 담아 주었다. 시작점을 기준으로 가장 멀리 있는 값을 temp라는 변수에 갱신시키며 해당 BFS 알고리즘에서 가장 큰 값을 가져오려 하였다.

3) 시작점을 어디에 잡는지가 중요한 문제이기에, 들어갈 수 있는 모든 'L'(땅을 설치하였다) 같은 군집의 땅이라도 시작점에 따라서, 최대 값이 달리 나올 수 있기에, 매번 visited 배열을 초기화 하므로써 가장 먼 두 점 사이를 구하려 노력하였다.

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;

int n, m;
char arr[51][51];
bool visited[51][51];
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
int ans = 0;

void visitClear()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			visited[i][j] = false;
	}
}
int bfs(int a, int b)
{
	visited[a][b] = true;
	queue < pair<int, pair<int, int>>> q;
	q.push({ a,{b,0} });
	int temp = 0;
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second.first;
		int cnt = q.front().second.second;
		q.pop();
		temp = max(temp, cnt);
		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)
				continue;
			if (arr[nextX][nextY] == 'L' && !visited[nextX][nextY])
			{
				visited[nextX][nextY] = true;
				q.push({ nextX,{nextY,cnt + 1} });
			}
		}
	}
	return temp;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++)
		{
			arr[i][j] = s[j];
		}
	}


	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (arr[i][j] == 'L' && !visited[i][j])
			{
				ans = max(bfs(i, j), ans);
				visitClear();
			}
		}
	}
	cout << ans;
}