[백준] 2589 보물섬

https://acmicpc.net/problem/2589 

2589번: 보물섬

from collections import deque
n, m = map(int, input().split())
_map = [ input() for i in range(n)]
# n, m = 5, 7
# _map = ['WLLWWWL', 'LLLWLLL', 'LWLWLWW', 'LWLWLLL', 'WLLWLWW']

def bfs(x, y):
    q = deque()
    visited = [[0] * m for _ in range(n)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    q.append((x, y))
    visited[x][y] = 1
    cnt = 0
    size = len(q)
    distance = 1
    while q:
        if cnt == size:
            cnt = 0
            size = len(q)
            distance += 1
        cnt += 1
        nx, ny = q.popleft()
        for i in range(4):
            if 0 > nx + dx[i] or n <= nx + dx[i]: continue
            if 0 > ny + dy[i] or m <= ny + dy[i]: continue
            if _map[nx + dx[i]][ny + dy[i]] == 'W': continue
            if visited[nx + dx[i]][ny + dy[i]]: continue
            q.append((nx + dx[i], ny + dy[i]))
            visited[nx + dx[i]][ny + dy[i]] = distance
    return distance - 1

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

python에서 시간초과가 나길래 pypy로 되는지만 확인하였는데 성공하였다. 130292 kb / 696 ms

이제 파이썬에서 시간을 줄여보자...

꽤 오래 했는데 계속 시간초과가 뜬다.

여기까지만 해야겠다

pypy는 꽤 빨리 끝나는데 왜 파이썬은 안되냐...