[Python] 백준 <2589-보물섬>

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

 

from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split(" "))
main_map = []
for _ in range(N):
    main_map.append(list(input()))

def bfs(i, j):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    dq = deque()
    # deque에 x, y, 시간 저장
    dq.append((i, j, 0))
    visited = [[0]*M for _ in range(N)]
    visited[i][j] = 1
    cnt = 0

    while dq:
        x, y, time = dq.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            # 맵 안에 있고 방문하지 않았고 육지면 가기
            # 거리(시간) 최대값 구하기 (한번 갈때마다 시간+1해서 저장)
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0 and main_map[nx][ny] == 'L':
                visited[nx][ny] = 1
                dq.append((nx, ny, time+1))
                cnt = max(cnt, time+1)

    return cnt


dap = 0

for i in range(N):
    for j in range(M):
        # 모든 육지 땅에 대해서 BFS 수행
        if main_map[i][j] == 'L':
            max_dis = bfs(i, j)
            dap = max(dap, max_dis)

print(dap)