[백준] 2589 보물섬 / 자바(Java)

문제

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

2589번: 보물섬

 

---

해설

BFS를 사용하면 될 듯한 문제입니다.

단 문제의 조건에서 최단거리 중 가장 먼 곳의 거리를 구해야합니다. 다행히 각 섬별로가 아닌 단 한 가지 경우만 찾으면 되므로 2차원 배열에 지도 정보를 넣고 각 땅 별로 BFS를 통해 갈 수 있는 최대 거리를 구해 각각을 비교하는 방식으로 해결할 수 있는 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 Main {

    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;
        }
    }
}