🐹 보물섬

1. 문제 링크

2589번: 가르침

2. 코드

PyPy3 116128KB 1008ms

from collections import deque

n, m = map(int, input().split())
Map = []
land = []
for _ in range(n):
    Map.append(list(input()))

# 땅 위치 저장
for i in range(n):
    for j in range(m):
        if Map[i][j] == 'L':
            land.append((i, j))

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

result = 0
for lx, ly in land:
    distance = [[0] * m for _ in range(n)]
    max_d = 0
    q = deque([(lx, ly)])
    distance[lx][ly] = 1
    while q:
        x, y = q.popleft()
        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] == 'L' and distance[nx][ny] == 0:
                distance[nx][ny] += distance[x][y] + 1
                max_d = max(max_d, distance[nx][ny])
                q.append((nx, ny))
    
    result = max(result, max_d-1)
    
    
print(result)
    

3. 해설

모든 L 좌표를 시작점으로 하여 bfs로 최단 거리를 찾았을 때의 최댓값을 구한다.