[백준] 2589번: 보물섬

문제 바로가기: https://www.acmicpc.net/problem/2589

2589번: 보물섬

 

육지 위 기준 거리가 가장 긴 곳에 보물이 묻혀있다. 최단경로 문제이니 너비우선탐색을 통해 문제를 구상했고,

가장 긴 경로를 찾기 위해서 모든 L에서 bfs를 진행한 후 나오는 가장 큰 거리 값을 답으로 하는 방식으로 문제를 풀었다.

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

//L = 76 , W = 87
int N,M;
//true는 Land, false는 Water
bool land[50][50];
bool visited[50][50];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

//visited 배열을 false로 초기화
void visitedInit()
{
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<M; j++)
		{
			visited[i][j] = false;
		}
	}
}

bool isInRange(int r, int c)
{
	if(r >= 0 && r <= N &&
		c >= 0 && c <=M)
		return true;
	else
	return false;
}

//bfs를 통해 배열을 순회한 뒤 가장 큰 거리 값을 반환
int bfs(int r, int c)
{
	int count = 0; 
	int dist = 0;
	queue<int> q;
	
	visitedInit();
	q.push(r), q.push(c); q.push(dist);
	
	
	visited[r][c] = true;
	
	while(!q.empty())
	{
		int tmpR, tmpC, tmpD;
		tmpR = q.front(); q.pop();
		tmpC = q.front(); q.pop();
		tmpD = q.front(); q.pop();
		
		if(tmpD > count)
		{
			count = tmpD;
		}
		
		for(int i=0; i<4; i++)
		{
			if(isInRange(tmpR+dx[i],tmpC+dy[i]) && visited[tmpR+dx[i]][tmpC+dy[i]] == false &&
			land[tmpR+dx[i]][tmpC+dy[i]])
			{
				visited[tmpR+dx[i]][tmpC+dy[i]] = true;
				q.push(tmpR+dx[i]);
				q.push(tmpC+dy[i]);
				q.push(tmpD+1);
			}
		}
	}
	
	return count;
}

//for문을 통하여 모든 Land로 부터 bfs를 통해서 가장 큰 distance를 구함
int getLongDist()
{
	int ret=0,tmp;
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<M; j++)
		{
			if(land[i][j])
			{
				tmp = bfs(i,j);
				if(tmp > ret)
				{
					ret = tmp;
				}
			}
		}
	}
	
	return ret;
}


void init()
{
	int tmp;
	cin >> N >> M;
	scanf("\n");
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<M; j++)
		{
			scanf("%1c",&tmp);
			if(tmp == 76)
			{
				land[i][j] = true;
			}
		}
		scanf("\n");
	}
}

int main() {
	init();
	int answer = getLongDist();
	cout << answer;
	return 0;
}