[백준] 2589. 보물섬

[문제]

 

www.acmicpc.net/problem/2589

2589번: 보물섬

[풀이]

 

 두 보물간의 최단거리를 구하는 문제.

최단거리를 구하는 문제이길래 BFS를 사용해서 풀려고 했다.

 

하지만 보물의 위치가 어딘지 몰라서 시작점과 도착점을 설정하는 데 있어 어려움을 겪었다.

 

생각해보니 map의 최대 사이즈는 50*50이라서 모든 육지에 대해서 시작점으로 잡고 최단거리를 구해도 되겠다고 생각을 하였다.

 

따라서 모든 육지에 대해 출발점으로 잡고 BFS 함수에서 최단거리를 구해 그 중에서도 가장 먼 거리를 정답으로 하도록 구현하였다. 

 

 

[코드]

 

시간 : 140ms

 

#include <iostream>
#include <queue>
#include <cstring>

#define MAX 51

using namespace std;

struct pos{
    int x,y;
};
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

bool map[MAX][MAX]={0,};
int visited[MAX][MAX]={0,};
int N,M;

int BFS(int x,int y)
{
    memset(visited,0,sizeof(visited));
    
    queue <pos> q;
    q.push({x,y});
    visited[x][y]=1;
    int res =0;
    
    while(!q.empty()){
    
        int x= q.front().x;
        int y= q.front().y;
        
        if(res < visited[x][y]) res= visited[x][y];
        
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]!=0 || map[nx][ny] )  continue;
            
            q.push({nx,ny});
            visited[nx][ny]=visited[x][y]+1;
            
        }
    }
    
    return res;
}

int main(void){
    
    cin >> N >> M;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            char ch;
            cin >> ch;
            if(ch == 'W')   map[i][j]=true;
        }
    }
    
    int ans =0;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(map[i][j]==0){
                int res = BFS(i,j);
                if(res > ans )  ans = res;
            }
        }
    }
    cout << ans-1;
    return 0;
}