[Algorithm/Java] 백준 2589번 - 보물섬

---

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

---

🔍 문제 풀이

풀이 방법

최단거리 중 최댓값을 구하는 문제이다.

• 지도에서 육지(L)이고 아직 방문하지 않은 칸을 시작점으로 BFS를 수행하였다.
• 각 BFS는 시작점에서 가장 먼 칸까지의 최단거리를 구한다.
• 그 중 최댓값을 출력하면 된다.

💻 코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static char[][] arr;
    static int[][] v;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};


    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // input
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new char[n][m];

        for(int i=0; i<n; i++) {
            String line = br.readLine();
            for(int j=0; j<m; j++) {
                arr[i][j] = line.charAt(j);
            }
        }

        // solve
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(arr[i][j] == 'L') {
                    bfs(i, j);
                }
            }
        }

        // output
        System.out.println(max - 1);

    }
    static void bfs(int x, int y){
        // 1. 초기화
        Deque<Pos> dq = new ArrayDeque<>();
        v = new int[n][m];

        // 2. 초기값
        dq.offer(new Pos(x, y));
        v[x][y] = 1;

        // 3. 탐색
        while(!dq.isEmpty()) {
            Pos cur = dq.poll();
            max = Math.max(max, v[cur.x][cur.y]);

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

                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

                if(arr[nx][ny] == 'L' && v[nx][ny] == 0) {
                    v[nx][ny] = v[cur.x][cur.y] + 1;
                    dq.offer(new Pos(nx, ny));
                }
            }
        }
    }

    static class Pos{
        int x;
        int y;

        Pos(int x, int y){
            this.x = x;
            this.y = y;

        }
    }
}