[python] 백준 2589 보물섬

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

2589번: 보물섬

 

문제 해결

• 전형적인 bfs문제
• 그러나 시작점을 기준점으로 하여 모든 경우의 시작점에서 다 경우의 수를 계산해봐야 하는지 의문이 들었다.
• 50*50 지점이라 계산이 되겠지만 사실 다른 방법이 생각이 안났다.
• python3버전은 시간초과가 뜨고 pypy3버전은 통과를 한다.
• 시간 문제에 대해서는 더 고민해봐야겠다.

 

CODE

from collections import deque
import sys
input = sys.stdin.readline
def bfs(x,y):
    dxs = [-1,1,0,0]
    dys = [0,0,-1,1]
    que = deque()
    que.append((x,y))
    visited = [[-1]*m for _ in range(n)]
    visited[x][y] = 0
    target = 0
    while que:
        a, b = que.popleft()
        for dx, dy in zip(dxs, dys):
            nx = a + dx ; ny = b + dy
            if 0<=nx<n and 0<=ny<m and visited[nx][ny] == -1 and graph[nx][ny] == 'L':
                visited[nx][ny] = visited[a][b] + 1
                target = max(target,visited[nx][ny])
                que.append((nx,ny))
    return target
if __name__=='__main__':
    n, m = map(int, input().split())
    graph = [[str(c) for c in input().rstrip()] for _ in range(n)]
    answer = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'L':
                answer = max(answer,bfs(i,j))
    print(answer)