🦊 보물섬

1. 문제 링크

2589번: 보물섬

2. 코드

Python3 31120KB 4972ms

delta = [[1, 0], [-1, 0], [0, 1], [0, -1]]
R, C = map(int, input().split())

MAP = []
for i in range(R):
    row = input()
    MAP.append(row)

def bfs(x, y):
    visit = [[0] * C for _ in range(R)]
    visit[i][j] = 1
    count = 0
    q = [(x, y)]
    while q:
        cx, cy = q.pop(0)
        for dx, dy in delta:
            nx = cx + dx
            ny = cy + dy
            if 0 <= nx < C and 0 <= ny < R and visit[ny][nx] == 0 and MAP[ny][nx] == 'L':
                visit[ny][nx] = visit[cy][cx] + 1
                count = max(count, visit[ny][nx])
                q.append((nx, ny))
    return count - 1

max_distance = 0
for i in range(R):
    for j in range(C):
        # 모든 육지에 대해 검사
        if MAP[i][j] == 'L':
            max_distance = max(bfs(j, i), max_distance)

print(max_distance)

3. 해설

모든 L 좌표에 대해 BFS 수행하여 Depth 가 최대인 것을 선택하면 보물이 위치한 장소끼리의 최단거리가 된다