문제

코드

import sys 
input = sys.stdin.readline
from collections import deque #BFS


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

def bfs(x,y):
    queue.append([x,y])
    timeGraph =[[0]*m for _ in range(n)] #임시그래프 생성 
    timeGraph[x][y]=1 #시간을위한 그래프
    time =0
    while queue:
      x,y = queue.popleft() #i.j삽입
      for i in range(4):
          cx = x+dx[i]
          cy = y+dy[i]
          if 0<=cx<n  and 0<=cy<m :
              if graph[cx][cy] == 'L' and timeGraph[cx][cy]==0: #아직탐색안한 육지
                  timeGraph[cx][cy] = timeGraph[x][y] + 1 #시간 더해나감 
                  time = max(time,timeGraph[cx][cy])
                  queue.append([cx,cy])
    return time-1 #있던자리빼기 

queue = deque()
n,m = map(int,input().split()) #세로,가로 
graph = [list(input().rstrip()) for _ in range(n)] #그래프 입력받기 
cnt = 0 

for i in range(n):
    for j in range(m):
        if graph[i][j] == 'L': #L이 저장된곳에 cnt 최댓값 출력 
            cnt=max(cnt,bfs(i,j)) 
print(cnt)

해설

이때까지의 문제와 약간 비슷한 맛이 있지만 이 문제에서는 하나를 더 생각해줘야한다.
그래서 골드인가?
무엇이냐면 이전에는 탐색했던 곳의 자리를 변경시켜주어서 다시 탐색하지 않게해서 너비우선탐색을 진행했었는데 이번 문제같은 경우는 탐색했던 곳의 자리를 변경해주면 안된다.
그 이유는 L로 연결된 길에서 각각의 케이스마다 보물의 위치와 최단거리를 만들어야하기 때문에 모든 케이스를 다 생각해줘야한다.
그래서 브루트 포스 문제인거같다!!

시간초를 재기 위한 timeGraph

그래프를 통해서 지도를 입력받고 타임그래프라는 그래프를 n,m크기로 새로 정의해주었다. 왜냐하면 이 그래프를 통해서 L이 있는 위치부터 1로 시작하여 탐색을 하여 시간을 저장할것이기 때문이다.
이렇게 탐색을 하고 time이라는 변수에 최댓값을 넣어주며 반복문을 진행한다.
이러면 모든 L을 탐색하고 모든 시간대를 탐색을 끝내면 그 최댓값인 time에 자기자리에 1을 뺀 값을 반환해주면된다.

핵심 조건

          if 0<=cx<n  and 0<=cy<m :
              if graph[cx][cy] == 'L' and timeGraph[cx][cy]==0: #아직탐색안한 육지

핵심조건은 이거다 !
두 그래프를 같이 겹쳐놔서 생각하면 더 편할것이다.