[백준 2589번] 보물섬

2589번: 보물섬

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

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

# L : 육지, W : 바다

max_value = float("-inf")

n, m = map(int,input().split())

area = [list(input().rstrip()) for _ in range(n)]

def bfs(x,y):

    global max_value

    visited = [[-1]*m for _ in range(n)]
    
    visited[x][y] = 0
    
    queue = deque([(x,y)])

    while queue:
        curr_x, curr_y = queue.popleft()

        max_value = max(max_value,visited[curr_x][curr_y])

        for i in range(4):
            nx = curr_x + dx[i]
            ny = curr_y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == -1 and area[nx][ny] == "L":
                visited[nx][ny] = visited[curr_x][curr_y] + 1
                queue.append((nx,ny))

for i in range(n):
    for j in range(m):
        if area[i][j]=="L":
            bfs(i,j)

print(max_value)

이번 문제는 육지(L)과 바다(W)로 표시된 영역에서 보물이 최단 거리가 가장 긴 육지 두곳에 위치한다고 했을 때, 보물이 묻혀 있는 두 곳의 최단 거리를 구하는 문제이다.

 

결론적으로 이 문제에서 구하고자 하는 것은 '해당 영역에 존재하는 특정 지점에서 출발한 최단거리의 최댓값'이다.

 

따라서 BFS로 최단거리를 구하기 위해 deque 라이브러리를 사용했고, 매 경로의 이동거리를 저장하기 위한 visited 배열을 선언한 뒤, 최단거리의 최댓값(max_value)를 갱신해주는 방식으로 풀이하였다.

 

(참고로 pypy3로 풀이해야 시간초과가 발생하지 않는다.)

 

BFS 알고리즘을 복습할 수 있었던 간단한 문제였다 :)