[백준] C++ 2589번(보물섬)

 

#include <iostream>
#include <queue>

using namespace std;

int arr[51][51];

int BFS(int i, int j);

int row=0;
int col=0;

int visited[51][51];

int main(void)
{

	cin>>row>>col;
	
	for(int i=0; i<row; i++)
	{
		for(int j=0; j<col; j++)
		{
			char c1;
			cin>>c1;
			if(c1=='L')
			{
				arr[i][j]=1;
			}
			else
			{
				arr[i][j]=0;
			}
		}
	}
	int max=0;
	
	for(int i=0; i<row; i++)
	{
		for(int j=0; j<col; j++)
		{
			if(arr[i][j]==1)
			{
				int temp=BFS(i,j);
				if(max<temp)
				{
					max=temp;

				}
				for(int m=0; m<row; m++)
				{
					for(int l=0; l<col; l++)
					{
						visited[m][l]=0;
					}
				}
				
			}
			
		}
	}

	cout<<max<<endl;
	
	return 0;
}

int BFS(int i, int j)
{
	queue<pair<int,int>> Q;
	queue<int> Q2;
	int result=0;
	
	Q.push(make_pair(i,j));
	Q2.push(0);
	
	visited[i][j]=1;
	
	while(!Q.empty())
	{
		int num1=Q.front().first;
		int num2=Q.front().second;
		int count=Q2.front();
		result=count;
		Q.pop();
		Q2.pop();
		
		if(arr[num1+1][num2]==1 && visited[num1+1][num2]==0 && num1+1<row)
		{
			Q.push(make_pair(num1+1,num2));
			Q2.push(count+1);
			visited[num1+1][num2]=1;
		}
		if(arr[num1-1][num2]==1 && visited[num1-1][num2]==0 && num1-1>-1)
		{
			Q.push(make_pair(num1-1,num2));
			Q2.push(count+1);
			visited[num1-1][num2]=1;
		}
		if(arr[num1][num2+1]==1 && visited[num1][num2+1]==0 && num2+1<col)
		{
			Q.push(make_pair(num1,num2+1));
			Q2.push(count+1);
			visited[num1][num2+1]=1;
		}
		if(arr[num1][num2-1]==1 && visited[num1][num2-1]==0 && num2-1>-1)
		{
			Q.push(make_pair(num1,num2-1));
			Q2.push(count+1);
			visited[num1][num2-1]=1;
		}
		
	}
	
	return result;
}

 

이 문제는 보물의 거리를 구하는 문제이다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 

 

 

나는 너비 우선 탐색을 기반으로 육지인 곳을 모두 탐색하여 해결하였다. (for 문을 돌면서 L인 곳에서 BFS를 실행, W인 곳에서는 BFS를 실행하지 않는다) (BFS에서는 한 칸 지날 때 마다 count++를 하고 최댓값을 찾아내면 된다. 위 그림은 8이 최댓값이다.)

 

알아보니까 queue<<int>,pair<int,int>> Q;이렇게 사용하기도 한다. 

내가 해결한 방식은 시간복잡도 측면에서 좋은 성능을 내지 못한다. 조금 더 효율적으로 해결하는 방법을 찾아보는 것이 좋아보인다.