[골드5] 2589번 : 보물섬

🛠 문제

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

👩🏻‍💻 해결 방법

모든 L의 좌표를 시작점으로 생각해서 가장 먼 곳을 최단거리로 가는 시간을 bfs를 통해 하나씩 구해주며 값을 갱신해주었다
시간초과가 나서 pypy3를 이용해 제출했다

소스 코드

from collections import deque

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

def bfs(i, j, visit):
  q = deque()
  q.append((i, j))
  visit[i][j] = 0
  
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0<=nx<n and 0<=ny<m and graph[nx][ny] == 'L':
        if visit[nx][ny] == -1:
          visit[nx][ny] = visit[x][y] + 1
          q.append((nx, ny))

n, m = map(int, input().split())
graph = []
land = []
for i in range(n):
  graph.append(list(input()))
  for j in range(m):
    if graph[i][j] == 'L':
      land.append([i, j])

answer = 0
for [i, j] in land:
  visit = [[-1] * m for _ in range(n)]
  bfs(i, j, visit)
  max_v = 0
  for v in visit:
    max_v = max(max_v, max(v))
  answer = max(answer, max_v)

print(answer)