이번 문제는 모든 L 좌표에서의 BFS의 결과값의 최댓값을 구하는 방식으로 해결하였다. 처음에는 이 방식이 시간 초과가 발생할 것이라 우려하여 생각하지 않았지만, 세로 가로의 최댓값이 50이었기 때문에 시간초과가 발생하지 않는 다는 것을 알게 되었고, 이 방식으로 쉽게 해결할 수 있었다.

Code

from collections import deque
n, m=map(int, input().split())
grid=[list(str(input())) for _ in range(n)]
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
def bfs(y, x):
    q=deque()
    q.append((y, x, 0))
    visited=[[False for _ in range(m)] for _ in range(n)]
    visited[y][x]=True
    result=0
    while q:
        y, x, dist=q.popleft()
        result=max(result, dist)
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<n and 0<=nx<m and not visited[ny][nx] and grid[ny][nx]=='L':
                visited[ny][nx]=True
                q.append((ny, nx, dist+1))
    return result
answer=0
for i in range(n):
    for j in range(m):
        if grid[i][j]=='L':
            answer=max(answer, bfs(i, j))
print(answer)