[백준/파이썬] 2589 보물섬

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

---

알고리즘 분류

• 브루트포스
• BFS

문제풀이

L의 위치마다 함수실행을 한다.
해당 함수에서는 그 L과 다른 위치의 L간의 거리중 최대값을 저장한다.(cnt)

소스코드

from collections import deque

n,m=map(int, input().split())
maps=[]
for i in range(n):
  maps.append(list(input()))

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

def bfs(i,j):
  queue=deque()
  queue.append((i,j))
  visited=[[0]*m for _ in range(n)]
  visited[i][j]=1
  cnt=0
  while queue:
    x,y=queue.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=n or ny<0 or ny>=m:
        continue
      elif maps[nx][ny]=='L' and visited[nx][ny]==0:
        visited[nx][ny]=visited[x][y]+1
        cnt=max(cnt,visited[nx][ny])
        queue.append((nx,ny))
  return cnt-1

result=0
for i in range(n):
  for j in range(m):
    if maps[i][j]=='L':
      result=max(result,bfs(i,j))

print(result)