baekjoon 2589: 보물섬

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

2589번: 보물섬

---

bfs와 브루스포스 알고리즘으로 한칸씩 육지를 밟을때 시간을 체크해준다.

하나의 섬(?)에서 최단거리측정하는 방식으로 최대거리를 구하면 된다. #문제에 설명이 잘 되어있습니다ㅎㅎ.

그렇다면 코드는

from collections import deque
n, m = list(map(int,input().split()))
arr = [list(input())for _ in range(n)]
lst = [[0]*m for _ in range(n)]
result = 0
Max = -21e8
def bfs(y,x):
    global Max, cnt
    q = deque()
    q.append((y,x))
    directy = [-1,1,0,0]
    directx = [0,0,-1,1]

    while q:
        nowy,nowx = q.popleft()

        for i in range(4):
            dy = directy[i] + nowy
            dx = directx[i] + nowx

            if 0 <= dy < n and 0 <= dx < m and lst[dy][dx] == 0 and arr[dy][dx] != "W":

                lst[dy][dx] = lst[nowy][nowx] + 1
                Max = max(lst[dy][dx],Max)
                q.append((dy,dx))
    return Max

for i in range(n):
    for j in range(m):
        if arr[i][j] == 'L':
            lst = [[0] * m for _ in range(n)]
            arr[i][j] = 0
            lst[i][j] = 1
            result = max(result,bfs(i,j))
print(result-1)

가 된다!