2589번 보물섬

 기본적인 BFS 문제.

 

 1. 한 육지에서 시작.

 2. 다른 육지로 이동.

 3. 카운트 세면서 가장 긴 시간(최댓값)을 구한다.

 4. 다른 육지에서 시작하면서 1~3번을 실행한다.

 

  

#include <iostream>
#include <queue>
#define visited true
#define Non_visited false
#define MAX 51
 
using namespace std;
 
typedef pair<int,int> pir;
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
queue<pir> q;
int L,W;
char map[MAX][MAX];
bool v[MAX][MAX];
int cnt[MAX][MAX];
int ans;
 
void solved(int x, int y){
    
    q.push(pir(x,y));
    v[x][y]=visited;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x + xx[i];
            int ny = y + yy[i];
            
            if(nx<0 || ny<0 || nx>=L || ny>=W || map[nx][ny]=='W') continue;
            if(!v[nx][ny] && map[nx][ny]=='L'){
                v[nx][ny]=visited;
                cnt[nx][ny]=cnt[x][y]+1;
                ans=max(ans,cnt[nx][ny]);
                q.push(pir(nx,ny));
            }
        }
    }
}
 
void clear(){
    for(int i=0;i<L;i++){
        for(int j=0;j<W;j++){
            v[i][j]=Non_visited;
        }
    }
    
    for(int i=0;i<L;i++){
        for(int j=0;j<W;j++){
            cnt[i][j]=0;
        }
    }
}
 
int main(){
    cin >> L >> W;
    
    for(int i=0;i<L;i++){
        for(int j=0;j<W;j++){
            cin >> map[i][j];
        }
    }
    
    for(int i=0;i<L;i++){
        for(int j=0;j<W;j++){
            if(map[i][j]=='L'){
                solved(i,j);
                clear();
            }
        }
    }
    
    cout << ans << endl;
}