BOJ - 2589

백준 문제 링크
보물섬

❓접근법

1. BFS를 사용했다.
2. BFS 함수를 만들건데,
   함수 내에서 방문 처리할 2차원 리스트 visited,
   거리를 저장할 2차원 리스트 answer,
   보물 간 최단 거리를 저장할 변수 cnt 를 만든다.
3. 4 방향으로 움직이면서,

• 범위 안에 있고, 'W'가 아니면서, 아직 방문하지 않았다면
  방문 처리하고, 큐에 넣고, answer[nx][ny] 를 갱신하고,
  cnt = max(cnt, answer[nx][ny]) 로 갱신해준다.
  마지막으로는 return cnt로 함수를 마무리한다.

4. max_value = 0으로 지정하여
   graph에서 L인 좌표만 bfs 함수를 실행시켜 cnt를 반환받은 뒤
   최댓값을 계속 갱신하여 max_value가 최대가 되게 만들어주고 출력!

👌🏻코드

from collections import deque

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

graph = []
for _ in range(n):
    graph.append(list(input()))
    
def bfs(x, y):
    visited = [[False] * m for _ in range(n)]
    answer = [[0] * m for _ in range(n)]
    queue = deque()
    queue.append((x, y))
    
    visited[x][y] = True
    
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    cnt = 0
    while queue:
        x, y = queue.popleft()
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            
            if (0 <= nx < n) and (0 <= ny < m) and graph[nx][ny] != 'W':
                if not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    answer[nx][ny] = answer[x][y] + 1
                    cnt = max(cnt, answer[nx][ny])
                    
    return cnt

max_value = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'L':
            max_value = max(max_value, bfs(i,j))
            
print(max_value)