STUDY/Algorithm

[백준] 2589 보물섬

sinawi95 2021. 3. 8. 22:16
728x90

https://acmicpc.net/problem/2589 

 

2589번: 보물섬

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서

www.acmicpc.net

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