728x90
https://acmicpc.net/problem/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는 꽤 빨리 끝나는데 왜 파이썬은 안되냐...
'STUDY > Algorithm' 카테고리의 다른 글
[백준] 9663 N-Queen (0) | 2021.03.10 |
---|---|
[백준] 2580 스도쿠 (0) | 2021.03.09 |
[백준] 2468 안전영역 (0) | 2021.03.06 |
[백준] 1759 암호만들기 (0) | 2021.03.05 |
[백준] 3980 선발명단 (1) | 2021.03.05 |