백준 - 2589번 보물섬

보물섬

이 문제는 그래프 문제이고
인접 행렬의 BFS와 관련된 문제이다.

1. 인접 행렬에서의 BFS를 어떻게 처리하는가?
2. 인접 행렬에 BFS를 적용할 때 시간복잡도

를 알고 있다면 무리없이 풀 수 있다.

사실 원래 몰랐더래도 간단히 생각해보면
이차원 행렬에 대해 BFS를 적용해보면
최악의 케이스가 행렬의 모든 원소에 접근하는 케이스 일 테고

그러면 행과 열을 각각 N,M이라고 할 때
worst case가 대략 O(NM) 그니까 뭐 대충 O(N^2) 이다.

이 문제에서 모든 행렬의 가능한 시작지점을 고려해본다고 할 때,
모든 부분이 육지인 L 이어서 이차원 배열 전체를 뒤진다 해도
행과 열의 최대값이 50으로
50^4 정도의 연산이고 이는 625만 정도이니까

1초에 약 7000만 ~ 1억 연산을 한다는 C++로는
아주 여유롭게 처리할 수 있다.

소스 코드는 다음과 같다.

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
int arr[51][51]={0};
queue<pair<int,int>> q;
bool visited[51][51]={0};
int dist[51][51]={0};
int w,h;
int bfs(int x1,int y1);
void init();
int main(){
	cin>>w>>h;
	for(int i=1;i<=w;i++){
		for(int j=1;j<=h;j++){
			char c;
			cin>>c;
			if(c=='L'){
				arr[i][j]=1;
			}
			else arr[i][j]=0;
		}
	}
	int answer=0;
	for(int i=1;i<=w;i++){
		for(int j=1;j<=h;j++){
			answer=max(answer,bfs(i,j));
			init();
		}
	}
	cout<<answer<<'\n';
	
}
int bfs(int x1,int y1){
	int res = 0;
	if(arr[x1][y1]==0) return 0;
	visited[x1][y1]=true;
	dist[x1][y1]=0;
	q.push({x1,y1});
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		int dx[4]={0,0,1,-1};
		int dy[4]={1,-1,0,0};
		for(int i=0;i<4;i++){
			int rx = x+dx[i];
			int ry = y+dy[i];
			if(rx>w||rx<1||ry>h||ry<1) continue;
			if(visited[rx][ry]) continue;
			visited[rx][ry]=true;
			if(arr[rx][ry]){
				dist[rx][ry]=dist[x][y]+1;
				res=max(res,dist[rx][ry]);
				q.push({rx,ry});
			}
		}
	}
	return res;
}
void init(){
	for(int i=0;i<51;i++){
		for(int j=0;j<51;j++){
			dist[i][j]=0;
			visited[i][j]=false;
		}
	}
}