백준 2589번: 보물섬

문제 설명

• https://www.acmicpc.net/problem/2589
• 서로 연결되어있는 육지 중 가장 거리가 먼 두곳의 거리를 구하는 문제입니다.

접근법

• BFS로 연결된 섬을 구합니다. 이때 육지인 모든 곳에서 BFS를 실행합니다.
• 보통은 BFS로 연결된 위치를 방문처리 해 다시 BFS처리하지 않지만, 이번 문제는 모든 위치에서 최장거리를 구해야 하기 때문에 방문처리를 하지 않습니다.

정답

import java.util.*;

public class Main {
	static int[] dx = { 1, 0, -1, 0 }; // 남,동,북,서
	static int[] dy = { 0, 1, 0, -1 };
	static int N, M;
	static char[][] board;
	static int MaxVal = -1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		sc.nextLine();
		board = new char[N][M];
		for (int i = 0; i < N; i++) {
			board[i] = sc.nextLine().toCharArray();
		}
		boolean[][] v = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 'L') {
					BFS(new int[] { i, j });
				}
			}
		}
		System.out.println(MaxVal);

	}

	public static void BFS(int[] start) {
		boolean[][] v = new boolean[N][M];
		v[start[0]][start[1]] = true;
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(start);
		int cnt = 0;
		while (!q.isEmpty()) {
			int size = q.size();
			cnt++;
			while (--size >= 0) {
				int[] now = q.poll();
				for (int d = 0; d < 4; d++) {
					int nx = now[0] + dx[d];
					int ny = now[1] + dy[d];
					if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] == 'L' && !v[nx][ny]) {
						v[nx][ny] = true;
						q.add(new int[] { nx, ny });
					}
				}
			}
		}
		MaxVal = Math.max(MaxVal, cnt - 1);
	}
}