[JAVA]백준_2589_보물섬

문제 : www.acmicpc.net/problem/2589

2589번: 보물섬

문제 유형 : BFS

 

풀이방식 : 육지인 지점 마다 BFS 탐색하여 최대 LEVEL 측정

 

소스코드

package BOJ;

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 BOJ_2589_보물섬_Main {

	private static int result;
	private static int r;
	private static int c;
	private static char[][] map;

	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());
		map = new char[r][c];
		for (int i = 0; i < r; i++) {
			map[i] = br.readLine().toCharArray();
		}
		result = 0;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if(map[i][j]=='L') {
					bfs(i,j);
				}
			}
		}
		System.out.println(result);
	}

	private static void bfs(int i, int j) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.offer(new int[] {i, j});
		boolean[][] visited = new boolean[r][c];
		int count = 0;
		int[] dr = {0,0,1,-1}, dc = {1,-1,0,0};
		visited[i][j] = true;
		while(!q.isEmpty()) {
			int size = q.size();
			boolean flag = false;
			for (int s = 0; s < size; s++) {
				int[] cur = q.poll();
				for (int d = 0; d < 4; d++) {
					int nr = cur[0] + dr[d];
					int nc = cur[1] + dc[d];
					if(nr>-1&&nc>-1&&nr<r&&nc<c&&!visited[nr][nc]&&map[nr][nc]=='L') {
						flag = true;
						visited[nr][nc] = true;
						q.offer(new int[] {nr,nc});
					}
				}
			}
			if(!flag) break;
			count++;
		}
		if(count>result) result = count;
	}

}