[BOJ 2589] 보물섬 (JAVA)

https://www.acmicpc.net/problem/2589

2589번: 보물섬

import java.util.*;

public class P2589 {
    static int N, M;
    static int maxVal=0;
    static String[] board;
    static boolean[][] visited;
    static int[] dx={-1,1,0,0};
    static int[] dy={0,0,-1,1};
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        N=scan.nextInt();
        M=scan.nextInt();
        board=new String[N];
        for (int i=0; i<N; i++){
            board[i]=scan.next();
        }
        for (int i=0; i<N; i++){
            for (int j=0; j<M; j++){
                if (board[i].charAt(j)=='L'){
                    bfs(i,j);
                }
            }
        }
        System.out.println(maxVal);
    }
    public static void bfs(int x, int y){
        Queue<Pair> q=new LinkedList<>();
        visited=new boolean[N][M];
        q.add(new Pair(x,y,0));
        visited[x][y]=true;
        while (!q.isEmpty()){
            Pair p=q.poll();
            for (int i=0; i<4; i++){
                int nx=p.x+dx[i];
                int ny=p.y+dy[i];
                if (nx<0 || ny<0 || nx>=N || ny>=M)
                    continue;
                if (board[nx].charAt(ny)=='L' && !visited[nx][ny]){
                    visited[nx][ny]=true;
                    q.add(new Pair(nx, ny, p.dist+1));
                    maxVal=(maxVal<p.dist+1)?p.dist+1:maxVal;
                }
            }
        }
    }

    public static class Pair{
        int x;
        int y;
        int dist;
        public Pair(int x, int y, int dist){
            this.x=x;
            this.y=y;
            this.dist=dist;
        }
    }
}

브루트 포스+BFS로 접근하면 된다.

처음엔 최단거리만 보고 플로이드 워셜을 이용하는건가 했는데 그럴 필요 없다.

 

자바로 처음 백준을 풀어본다.

 

String 대신 char[][]를 써준다.

BufferedReader을 이용하면 속도가 빨라진다.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());