백준 2589 보물섬 (파이썬)

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

2589번: 보물섬

1. 입력받은 지도에서 L이면 bfs를 수행한다.

2. 가장 멀리 이동할 수 있는 거리를 구하면 그 값이 보물이 묻혀 있는 두 지점 간의 최단 거리이다

from collections import deque

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

def bfs(x, y):
    q.append([x, y])
    c = [[0]*m for _ in range(n)]
    c[x][y] = 1
    num = 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:
                if a[nx][ny] == 'L' and c[nx][ny] == 0:
                    c[nx][ny] = c[x][y] + 1
                    num = max(num, c[nx][ny])
                    q.append([nx, ny])
    return num-1

n, m = map(int, input().split())
a = [list(map(str, input())) for _ in range(n)]
q = deque()

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