BOJ 2589 보물섬

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/***
 * 시간제한: 1초, 메모리제한: 512MB
 * N <= 50
 * 아이디어: BFS를 이용해서 queue에 좌표값 뿐만아니라 이동시간을 함께 넣어 가장 긴 시간이 걸리는 값을 갱신해 나간다. 즉 최대 시간을 갱신.
 * 가장 긴 시간이 걸리는 값이 어딘지를 모르니까. L인 모든 좌표에서 하는 방법이 있을 것 같다. 그런데 어떻게 하면 좋을까? L인 좌표를 저장해놓고 모든 점에서 BFS를 해보자.
 */
public class Main {
    // 동, 서, 남, 북
    static int[] dy = {0, 0, 1, -1};
    static int[] dx = {1, -1, 0, 0};
    static char[][] map;
    static boolean[][] visited;
    static List<int[]> list = new ArrayList<>();
    static int N, M, res;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        for(int i=0; i<N; i++){
            String ch = br.readLine();
            for(int j=0; j<M; j++){
                map[i][j] = ch.charAt(j);
                if(map[i][j] == 'L') list.add(new int[]{i, j});
            }
        }

        for(int[] location : list){
            bfs(location[0], location[1]);
        }

        System.out.println(res);

    }
    static void bfs(int startY, int startX){
        visited = new boolean[N][M];

        visited[startY][startX] = true;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {startY, startX, 0});

        while(!queue.isEmpty()){
            int[] items = queue.poll();

            int y = items[0];
            int x = items[1];
            int time = items[2];

            for(int d=0; d<4; d++){
                int ny = y+dy[d];
                int nx = x+dx[d];

                if(ny < 0 || ny >= N || nx < 0 || nx >= M) continue;

                if(!visited[ny][nx] && map[ny][nx]=='L'){
                    visited[ny][nx] = true;
                    res = Math.max(res, time+1);
                    queue.offer(new int[]{ny, nx, time+1});
                }
            }
        }
    }
}