[BOJ][python] 2589. 보물섬

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

2589번: 보물섬

---

💡IDEA

BFS를 사용하는 문제이다.

가로 세로가 50 이하이므로 브루트 포스를 더불어 사용했다.

육지(L)인 곳 중 상하좌우로 이어진 곳 중 최단 거리로 이동할 수 있어야 한다. 거리를 재기 위해 큐에서 카운트를 세어준다. 반환 값은 계산한 거리 중 가장 큰 값을 반환한다.

모든 행렬을 순환하면서 모든 육지(L)를 확인하며 최단 거리로 이동하는 시간을 갱신하여 출력한다.

 

📌CODE

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

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

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def bfs(r, c):
    q = deque([(r, c, 0)])
    v = [[0]*M for _ in range(N)]
    v[r][c] = 1
    res = -1
    while q:
        cr, cc, cnt = q.popleft()
        res = max(res, cnt)
        for k in range(4):
            nr = cr + dr[k]
            nc = cc + dc[k]
            if 0<=nr<N and 0<=nc<M and arr[nr][nc]=='L' and not v[nr][nc]:
                q.append((nr, nc, cnt+1))
                v[nr][nc] = 1
    return res

ans = -1
for r in range(N):
    for c in range(M):
        if arr[r][c] == 'L':
            ans = max(ans, bfs(r, c))

print(ans)