2589-보물섬

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

2589번: 보물섬

이 문제는 가볍게 BFS 문제로 풀 수가 있다.

BFS를 돌릴 떄마다 각각의 max값을 구한 후, 그 값과 다음으로 나올 값을 비교하면서 가장 큰 값을 찾아나가면 된다.

package 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 N2589 {
    public static class Pos{
        int r,c,dist;
        public Pos(int r, int c, int dist){
            this.r = r;
            this.c = c;
            this.dist = dist;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());
        char[][] world = new char[row][col];
        Queue<Pos> q  = new LinkedList<>();
        for (int i = 0; i < row; i++) {
            String a = br.readLine();
            for (int j = 0; j < col; j++) {
                world[i][j] = a.charAt(j);
            }
        }

        int maximum = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(world[i][j] == 'L'){
                    boolean[][] visited = new boolean[row][col];
                    q.add(new Pos(i,j,0));
                    visited[i][j] = true;
                    int result = Bfs(world,visited,row,col,q);
                    if(maximum < result){
                        maximum = result;
                    }
                }
            }
        }
        System.out.println(maximum);


    }

    public static int Bfs(char[][] world, boolean[][] visited, int row, int col,Queue<Pos> q){
        int max = 0;
        int[] DR = {1,0,-1,0};
        int[] DC = {0,1,0,-1};
        while(!q.isEmpty()){
            Pos Cur = q.poll();
            if(Cur.dist>max){
                max = Cur.dist;
            }
            for (int i = 0; i < DR.length; i++) {
                int nextR = Cur.r + DR[i];
                int nextC = Cur.c + DC[i];

                if(nextR < 0 || nextC < 0 || nextR >= row || nextC >= col) continue;

                if(world[nextR][nextC] == 'L' && !visited[nextR][nextC]){
                    visited[nextR][nextC] = true;
                    q.add(new Pos(nextR,nextC,Cur.dist+1));
                }
            }
        }
        return max;
    }
}