[C++][백준] [BFS] 2589 보물섬

https://www.acmicpc.net/problem/2589

2589번: 보물섬

문제

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

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

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

입력

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

출력

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

예제 입력 1

5 7

WLLWWWL

LLLWLLL

LWLWLWW

LWLWLLL

WLLWLWW

예제 출력 1

8

 

bfs를 이용해 풀 수 있는 문제이다.

최단거리를 구하는 문제인데 육지와 바다를 고려해야한다.

육지에서 바다로 나아가지 못하기 때문에 bfs를 이용해서 육지인 곳으로 나아가면서 구한다.

 

#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <queue>
using namespace std;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
char map[50][50] ={0};
bool visit[50][50] = {false};
int t=0;
int n,m;
 
void bfs(int x, int y){
    int path = 0;
    memset(visit, 0, sizeof(visit));
    queue< pair<int, int> > q;
    q.push(make_pair(x, y));
    visit[x][y] = true;
 
    while (!q.empty()){
        int qsize = q.size();
 
        for (int i = 0; i < qsize; ++i){
            int cur_x = q.front().first;
            int cur_y = q.front().second;
            q.pop();
 
            for (int j = 0; j < 4; ++j){
                int nx = cur_x + dx[j];
                int ny = cur_y + dy[j];
 
                if (!(0 <= nx && nx < n && 0 <= ny && ny < m)) continue;
                if (map[nx][ny] == 'W') continue;
                if (visit[nx][ny]) continue;
 
                q.push(make_pair(nx, ny));
                visit[nx][ny] = true;
            }
        }
        ++path;
    }
    if (t < path - 1) t = path - 1;
}
 
 
int main(){
    scanf("%d %d", &n, &m);
    
    for (int i = 0; i < n; ++i)
        scanf("%s", &map[i]);
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            if (map[i][j] == 'L')
                bfs(i, j);
                
    printf("%d\n", t);
  
}