[백준] 2589번 보물섬

💡문제접근

• 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 양 끝 육지에 하나씩 나뉘어 묻혀있다.
• 이중 반복문을 통해서 육지를 찾고 각각의 육지에서부터 육지의 끝까지 이동하는데 걸리는 시간을 BFS 함수를 이용해 찾아 최댓값을 출력하면 된다.

💡코드(메모리 : 124384KB, 시간 : 876ms, PyPy3로 제출)

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

N, M = map(int, input().strip().split())
Map = [list(input().strip()) for _ in range(N)]

def BFS(a, b):
    time = 0
    queue = deque()
    queue.append((a, b))
    # 육지인 L의 경우라면 BFS 함수가 실행되므로 함수 내에 선언해서 각각의 육지 좌표에 따른 최단거리를 계산하여 최댓값을 출력
    visited = [[0] * M for _ in range(N)]
    visited[a][b] = 1
    while queue:
        x, y = queue.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if Map[nx][ny] == "W":
                continue
            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0 and Map[nx][ny] == "L":
                visited[nx][ny] = visited[x][y] + 1
                time = max(time, visited[nx][ny])
                queue.append((nx, ny))
    return time-1

result = 0
for i in range(N):
    for j in range(M):
        if Map[i][j] == "L":
            result = max(result, BFS(i, j))
print(result)

💡소요시간 : 14m