[2589] 보물섬

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

---

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

// 보물섬 -> BFS
public class Main {

	static int N, M, minute, max;
	static char[][] map;
	static boolean[][] visited;
	static Queue<Pair> queue;
	static int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		map = new char[N][M];
		
		for (int i = 0; i < N; i++) {
			String st = sc.next();
			for (int j = 0; j < M; j++) {
				map[i][j] = st.charAt(j);
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				minute = 0;
				if (map[i][j] == 'L') {
					visited = new boolean[N][M];
					BFS(i, j);
					minute--;
					max = Math.max(minute, max);
				}
			}
		}
		System.out.println(max);
	}

	public static void BFS(int x, int y) {
		queue = new LinkedList<Pair>();
		queue.offer(new Pair(x, y));

		while (!queue.isEmpty()) {

			int len = queue.size();
			minute++;
			
			for (int i = 0; i < len; i++) {
				Pair p = queue.poll();
				visited[p.x][p.y] = true;

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

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

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

}

class Pair {
	int x;
	int y;

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

---

주어지는 두 곳의 육지에 보물이 2개 숨겨져 있는데, 각 육지에서 가장 멀리 떨어져있는 거리에 보물이 숨겨져 있습니다. 그래서 보물이 숨겨져 있는 거리의 가장 최댓값을 찾는 문제입니다. 보물간의 거리는 최솟값으로 이동해야합니다.

그래서 저는 육지중에서 2곳 선택할 수 있는 모든 경우의 수를 구해서 각 보물의 거리중에 최댓값을 구하려고 했습니다. 근데 생각해보니까 그렇게 안하고 각 육지의 모든 곳에서 BFS를 해서 최댓값을 구하면 간단하게 풀 수 있는 문제였습니다. 조합을 사용해서도 풀 수 있을 것 같은데, 그건 나중에 시도해봐야겠습니다.

처음에 이 문제를 풀 때 메모리 초과가 나와서 당황했는데, 검색해보니까 BFS를 할 때 visited를 제대로 안해주면 방문했던 곳을 다시 방문하기 때문에 메모리 초과가 나오는 것이었습니다. 이 부분을 조심해야 합니다.

[ 문제 풀이 ]

1. 주어진 map을 입력받고, 육지를 나타내는 "L" 에서 BFS 해서 몇번만에 모든 육지를 탐색하는지 minute에 저장합니다.

2. 한번 BFS 시도할 때 마다 minute을 비교해서 최댓값을 저장하고 출력하면 정답이 나옵니다.