#백준_2589 보물섬 - Java 자바

# 유형 : 그래프 탐색, BFS

# 난이도 : 골드 5

# 기존 bfs 문제와 비슷한데, 모든 육지에서 bfs를 돌려 가장 긴 구간을 구해야 했던 문제.

하나의 연결된 육지에서 가장 멀리 떨어져있는 두 곳을 찾아야한다. 아래의 경우 (1,2)에서 출발하는 건 최단 경로가 아니고, (4,1)에서 출발하여 (5,2)로 도착하는게 최단경로이다. 따라서 모든 육지에서 bfs를 돌려 가장 긴 값을 찾으면 된다.

 

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2589 {
    static int R,C;
    static int moveY[] = {-1,0,1,0};
    static int moveX[] = {0,1,0,-1};
    static char arr[][];
    static boolean visit[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new char[R][C];
        visit = new boolean[R][C];
        for(int i=0; i<R; i++) {
            String str = br.readLine();
            for(int j=0; j<C; j++) {
                arr[i][j] = str.charAt(j);
            }
        }
        int result = 0;
        
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(arr[i][j] == 'L') {
                    visit = new boolean[R][C];
                    int val = bfs(i,j);
                    result = Math.max(result, val);
                    
                }
            }
        }
        
        System.out.println(result);
        
    }
    private static int bfs(int i, int j) {
        Queue<Po> queue = new LinkedList<>();
        int val = 0;
        visit[i][j] = true;
        queue.add(new Po(j,i,0));
        while(!queue.isEmpty()) {
            Po p = queue.poll();
            for(int d=0; d<4; d++) {
                int newX = p.x + moveX[d];
                int newY = p.y + moveY[d];
                if(0<=newX && newX<C && 0<=newY && newY<R && !visit[newY][newX] && arr[newY][newX]=='L') {
                    visit[newY][newX] = true;
                    queue.add(new Po(newX, newY, p.cnt+1));
                    val = Math.max(val, p.cnt+1);
                }
            }
        }
        return val;
    }
    public static class Po{
        int x;
        int y;
        int cnt;
        public Po(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}