보물섬

 

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

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
int n, m;
char arr[51][51];
int visited[51][51];
int ret;
int Count;

void BFS(int x, int y)
{
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int>>q;
    q.push({x, y});
    visited[x][y] = 1;

    while (q.empty() == false)
    {
        int currx = q.front().first;
        int curry = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = dx[i] + currx;
            int ny = dy[i] + curry;

            if(nx >= 0 && nx < n && ny >= 0 && ny < m)
            {
                if(visited[nx][ny] == 0 && arr[nx][ny] == 'L')
                {
                    visited[nx][ny] = visited[currx][curry] + 1;
                    q.push({ nx,ny });

                    ret = max(ret, visited[nx][ny]);
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if(arr[i][j] == 'L')
                BFS(i, j);

    cout << ret - 1<< endl;
}

• 문제를 살짝 잘못읽어 고민을 많이 했었다
• 문제에 '보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다.'를 보지 못했던 것이다
• 이 문제는 BFS를 이용해 깊이를 측정해 가장 깊은 깊이를 찾는 문제로 BFS를 구현한 후 깊이를 비교하면 되는 문제이다