[백준] 2589번 보물섬

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

2589번: 보물섬

문제: 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다.  문제 풀이 : 최단 거리이기 때문에 BFS를 활용해서 풀었습니다. 사방 탐색을 하며 연결된 map을 갈 때마다 큐의 사이즈를 재어주어 count 를 늘려주었습니다. 이후 answer 변수를 주어 count 중 가장 큰 수를 출력해줍니다. 가장 긴 시간이 걸리는 것으로 답입니다.  몰랐던 점 : 방문 처리를 제대로 안해줘서 메모리 초과가 났다.

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 Solution {
	static int M, N, count = 0, answer = 0;
	static char[][] map;
	static int[][] dir = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
	static boolean[][] visited;
	static Queue<Pair> queue;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());

		map = new char[M][N];
		visited = new boolean[M][N];
		queue = new LinkedList();

		for (int i = 0; i < M; i++) {
			String ss = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = ss.charAt(j);
			}
		} // end of input

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 'L') {

					bfs(i, j);
					visited = new boolean[M][N];
				}
				answer = Math.max(count,answer);
				count = 0;
			}
		}

		System.out.println(answer - 1);

	}

	public static void bfs(int i, int j) {
		queue.add(new Pair(i, j));

		while (!queue.isEmpty()) {
			int len = queue.size();
			count++;
			
			for (int l = 0; l < len; l++) {

				Pair p = queue.poll();
				visited[p.x][p.y] = true;//

				for (int k = 0; k < dir.length; k++) {
					int nx = p.x + dir[k][0];
					int ny = p.y + dir[k][1];

					if (isInside(nx, ny) && !visited[nx][ny] && map[nx][ny] == 'L') {
						queue.offer(new Pair(nx, ny));
						visited[nx][ny] = true;//

					}
				}
			}
		}
	}

	public static boolean isInside(int x, int y) {
		return x >= 0 && x < M && y >= 0 && y < N;
	}
}

class Pair {
	int x;
	int y;

	Pair(int x, int y) {
		this.x = x;
		this.y = y;
	}

}