문제 정리

---

지도에서 서로간의 이동시간이 제일 오래걸리는 두 지점에 보물이 묻혀있다.
일부러 돌아가는건 안되고, 같은 곳을 두번 가는것도 안된다.
이 제일 오래걸리는 시간을 구하는것이 목표다.

입력

N M      //N: 행 크기 M: 열 크기
배열 정보     //L은 육지, W는 바다

출력

보물이 묻힌 지점 사이의 최단거리

idea 정리

---

육지인 곳에서 bfs를 돌아서 level이 가장 큰 지점을 찾으면 된다.
지도의 지점을 다 확인하기 싫으니 육지인 곳만 queue에 넣고 하나씩 빼서
bfs를 돌아준다.

---

더 짧게 나온 코드가 있길래 구경해보니 bfs를 도는 지점을 걸러내는 작업이 있었다.
연결된 육지들이 일자로 쭉 뻗은 모양인지 확인하는거 같은데 이게 왜 되는지는 이해가 안 간다.

알고리즘 구성

---

1. 육지인 곳만 queue에 넣어준다.
2. queue에서 하나씩 뽑아 bfs를 돈다.
3. bfs가 몇 레벨까지 도는지 확인해 최댓값을 갱신해준다.
4. queue가 빌 때까지 2~3 반복
5. 최댓값 출력

구현

---

//보물섬
public class Main {
	static class Land {
		int r, c;

		public Land(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}

	static int R, C;
	static char[][] map;
	static int max = Integer.MIN_VALUE;

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];
		
		Queue<Land> q = new LinkedList<>();

		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				if (map[i][j] == 'L')
					q.add(new Land(i, j));
			}
		}

		while (!q.isEmpty()) {
			bfs(q.poll());
		}

		bw.write(max + "");
		bw.flush();
		bw.close();
		br.close();
	}

	static void bfs(Land first) {
		Queue<Land> q = new LinkedList<>();
		q.add(first);
		boolean[][] visited = new boolean[R][C];
		visited[first.r][first.c] = true;

		int cnt = 0;

		while (!q.isEmpty()) {
			cnt++;
			for (int i = 0, size = q.size(); i < size; i++) {
				Land now = q.poll();

				for (int d = 0; d < 4; d++) {
					int nr = now.r + dr[d];
					int nc = now.c + dc[d];

					if (!isValidPosition(nr, nc) || visited[nr][nc] || map[nr][nc] == 'W')
						continue;
					visited[nr][nc] = true;
					q.add(new Land(nr, nc));
				}
			}
		} // end of while

		max = Math.max(max, cnt-1);
	}

	static boolean isValidPosition(int r, int c) {
		if (0 <= r && r < R && 0 <= c && c < C)
			return true;
		return false;
	}
}

결과

---