[알고리즘 BFS & DFS 5] TREASURE

문제

---

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 3이상 50이하이다.

 

출력

---

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

 

예제 입력

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

예제 출력

8

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

//백준 2589번
 
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
 
const int MAX = 55;
int arr[MAX][MAX];
int n, m;
int findSum = 0;
int sum = 0;
 
//좌표 구조체 생성
typedef struct coor{
  int x;
  int y;
  int cnt;
  coor(){};
  coor(int _x, int _y, int _cnt) :
  x(_x), y(_y), cnt(_cnt){};
}coor;
 
//4방면 확인
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
 
bool inside(int x, int y){
  return (x>=0 && x<n) && (y>=0 && y<m);
}
 
//큐생성
queue <coor> q;
 
//BFS
void BFS(){
  if(q.empty()) return;
  int x = q.front().x;
  int y = q.front().y;
  int cnt = q.front().cnt;
  q.pop();
  arr[x][y] = cnt;
  
  if(cnt>findSum) findSum = cnt;
  
  int nx, ny;
  for(int i=0; i<4; i++){
    nx = x + dx[i];
    ny = y + dy[i];
    if(inside(nx,ny) && arr[nx][ny] == 1){
      q.push(coor(nx,ny,cnt+1));
      //cout<<nx<<","<<ny<<","<<cnt<<endl;
    }
  }
  
  if(!q.empty()) BFS();
}
 
//맵 초기화
void reset(){
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(arr[i][j] != 0){
        arr[i][j] = 1;
      }
    }
  }
}
 
int main(){
  
  cin>>n>>m;
  char temp;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      scanf("\n%c\n",&temp);
      if(temp == 'L'){
        arr[i][j] = 1;
      }else if(temp== 'W'){
        arr[i][j] = 0;
      }
    }
  }
  
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(arr[i][j]==1){
        q.push(coor(i,j,2));
        findSum = 0;
        BFS();
        if(findSum > sum) sum = findSum;
        reset();
      }
    }
  }
  
  
  /*
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cout<<arr[i][j]<<" ";
    }
    cout<<endl;
  }
  */
  
  
  cout<<sum-2;
  
  
  
  return 0;
}