[Day 3] 백준 2589 : 보물섬

해법 : bfs

최단 거리들 중에서 최대값을 찾아야하는데 

map의 크기가 50*50이기 때문에 각각의 점들에 대해서 bfs를 각각 돌려도 시간복잡도가 충분히 나온다. 

 

 

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

int n,m;
int M[55][55];
int vt[55][55];
int que[2505][3];
int r,f;
int _max;
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};
void bfs(int x,int y) {
    que[r][0]=x;
    que[r][1]=y;
    que[r++][2]=1;
    int i,j;
    for(i=0;i<n;i++) {
        for(j=0;j<m;j++) {
            vt[i][j]=0;
        }
    }
    vt[x][y]=1;
    int p_x,p_y,p;
    //printf("%d %d\n",x,y);
    do {
        p_x=que[f][0];
        p_y=que[f][1];
        p=que[f++][2];
        //printf("%d %d %d\n",p_x,p_y,p);
        _max=max(_max,p);
        for(i=0;i<4;i++) {
            x=p_x+X[i];
            y=p_y+Y[i];
            if(x<0 || x>=n || y<0 || y>=m) continue;
            if(M[x][y]==1 && vt[x][y]==0) {
                que[r][0]=x;
                que[r][1]=y;
                que[r++][2]=p+1;
                vt[x][y]=1;
            }
        }
    } while(r>f);
}
int main() {
    //freopen("input.txt","r",stdin);
    scanf("%d %d",&n,&m);
    int i,j;
    char srg[55];
    for(i=0;i<n;i++) {
        scanf("%s",srg);
        for(j=0;j<m;j++) {
            if(srg[j]=='L') {
                M[i][j]=1;
            }
        }
    }
    for(i=0;i<n;i++) {
        for(j=0;j<m;j++) {
            //printf("%d ",M[i][j]);
            if(M[i][j]==1) {
                r=0,f=0;
                bfs(i,j);
            }
            //printf("\n");
        }

    }
    printf("%d\n",_max-1);
    return 0;
}