백준 2589 보물섬 (Java)

1. 문제 링크

2589번: 보물섬

 

2. 문제 및 입출력예제

 

3. 문제 풀이

최단 거리 중 가장 먼 거리를 찾는 것이다. (뭔가 말이 이상하지만)

bfs로 나온 거리들 중 가장 돌아서 가는 경우를 찾으면 된다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.io.IOException;

public class Main {
	static int N, M, result;
	static int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
	static boolean[][] map, visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		map = new boolean[N][M];
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			for(int j=0;j<M;j++) {
				if(str.charAt(j) == 'L') {
					map[i][j] = true;
				}
				else {
					map[i][j] = false;
				}
			}
		}
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j]) {
					bfs(i, j);
				}
			}
		}
		System.out.println(result);
	}

	private static void bfs(int x, int y) {
		int count = 0;
		Queue<int[]> queue = new ArrayDeque<>();
		visit = new boolean[N][M];
		
		queue.offer(new int[] {x, y});
		visit[x][y] = true;
		
		while(!queue.isEmpty()) {
			int size = queue.size();
			
			for(int i=0;i<size;i++) {
				int[] now = queue.poll();
				for(int d=0;d<4;d++) {
					int X = now[0]+dx[d];
					int Y = now[1]+dy[d];
					
					if(X<0 || X>=N || Y<0 || Y>=M || !map[X][Y] || visit[X][Y]) {
						continue;
					}
					
					queue.offer(new int[] {X, Y});
					visit[X][Y] = true;
				}
			}
			count++;
		}
		
		result = Math.max(result, count-1);
	}
}