[C/C++] 백준 2589번 - 보물섬

✏️ 문제 링크

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

 

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

그냥 단순히 모든 육지인 지점은 찾아서 그 지점에서 가장 먼 거리를 BFS를 탐색해서 구해준 후

거리들의 최댓값을 구해주면 됩니다

처음에는 트리의 지름을 구하는 방식으로 접근을 해봤는데 계속 2%에서 틀려서...

포기

 

 

✏️ 문제 코드

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

struct Node
{
	int y, x, depth;
};

const int dy[4] = { -1,1,0,0 };
const int dx[4] = { 0,0,-1,1 };

int N, M, ret;
char adj[50][50];
bool visited[50][50];
vector<pair<int, int>> v;

void bfs(int sy, int sx)
{
	// 초기화
	fill(&visited[0][0], &visited[0][0] + 50 * 50, false);
	queue<Node> q;

	// 첫 시작값
	q.push({ sy,sx,0 });
	visited[sy][sx] = true;

	while (q.size())
	{
		int y = q.front().y;
		int x = q.front().x;
		int depth = q.front().depth;
		q.pop();

		// 가장 depth가 큰거 찾기
		ret = max(depth, ret);

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

			if (ny < 0 || ny >= N || nx < 0 || nx >= M)
				continue;
			if (visited[ny][nx])
				continue;
			if (adj[ny][nx] == 'W')
				continue;

			visited[ny][nx] = true;
			q.push({ ny,nx,depth + 1 });
		}
	}
}



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;
	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++)
		{
			cin >> adj[y][x];
			// 육지인거 v에 넣기
			if (adj[y][x] == 'L')
				v.push_back({ y,x });
		}
	
	// 육지인 좌표 dfs
	for (int i = 0; i < v.size(); i++)
		bfs(v[i].first, v[i].second);

	cout << ret;


	return 0;
}