[백준/C++] 2589번 보물섬

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

2589번: 보물섬

오랜만에 푼 bfs 문제이다.

보물의 위치가 정해져있지 않기 때문에, 브루트포스를 이용하여 보물의 위치를 정해주는 것이 필요하다.

모든 육지(L)에 대해 bfs 탐색을 진행해주는데,

첫번째 L에 대해 bfs 탐색을 하고 얻게 된 가장 긴 길이가 5라고 할 때, bfs함수는 5를 반환하고 ans 변수에 저장한다.

지도를 초기화해준뒤, 2번째로 만나는 L에 대해 bfs 탐색을 하고 얻게 된 가장 긴 길이가 6이라면, bfs 함수는 6을 반환하고 ans변수에는 5가 아닌 6이 저장된다. 

보통 bfs와 브루트포스가 합쳐지면, 전체 지도에 대해 탐색을 진행하는 것이 아니라 탐색 가능한 각각에 대해 bfs를 해주면 된다.

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int n,m;
string s;
char board[51][51];
bool visited[51][51];
int arr[51][51],maxi;
queue<pair<int,int>> q;

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void reset(){
    memset(arr,0,sizeof(arr));
    memset(visited,false,sizeof(visited));
}

int bfs(int a, int b){
    q.push({a,b});
    arr[a][b]=0;
    visited[a][b]=true;

    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 + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || ny < 0 || nx >= n || ny >= m || board[nx][ny]=='W' || visited[nx][ny]) continue;

            visited[nx][ny]=true;
            arr[nx][ny] = arr[x][y]+1;
            q.push({nx,ny});
            if(maxi < arr[nx][ny]) {
                maxi = arr[nx][ny];
            }
        }
    }
    return maxi;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for(int i=0; i<n;i++){
        cin >> s;
        for(int j=0; j<s.size();j++){
            board[i][j]=s[j];
        }
    }
    int ans = -1;
    for(int i=0; i<n;i++){
        for(int j=0; j<m;j++){
            if(board[i][j]=='L') {
                int tmp = bfs(i,j);
                if(tmp > ans){
                    ans = tmp;
                }
            }
            reset();
        }
    }
    cout << ans;

    return 0;
}