코드

N,M = map(int,input().split(" "))

Maps = [list(map(str, input())) for _ in range(N)]

from collections import deque


dx = [-1,1,0,0]
dy = [0,0,-1,1]


def bfs(x,y):
    dist = [[0]*M for _ in range(N)]
    Q = deque([(x,y)])
    dist[x][y] = 1
    
    while Q:
        x,y = Q.popleft()

        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]

            if 0<=nx<N and 0<=ny<M and Maps[nx][ny]=="L" and dist[nx][ny]==0:
                    dist[nx][ny] = dist[x][y]+1
                    Q.append((nx,ny))


    return dist[x][y]-1


val = 0 

for i in range(N):  
    for j in range(M):
        if Maps[i][j]=="L":
            val = max(val,bfs(i,j))
print(val)

풀이

• visited를 따로 선언해주었더니 시간초과가 났다.
• 결국은 최단 거리를 구하면 되는 것이기 때문에, dist라는 것이 visited의 역할도 동시에 진행해주면 된다.
• dist가 0일 때만 Q에 append 하는 형식으로 if문을 걸어주면 된다.