백준 2589번 : 보물섬

 문제

www.acmicpc.net/problem/2589

2589번: 보물섬

2589 보물섬

 

 구현 방법

 이 문제는 약간 말장난.. 같습니다. 저도 처음에 한번에 이해를 못해서 몇 번이고 읽었습니다.

"보물은 서로 간에 최단 거리로 이동하는데 있어" -> 최단거리로 이동

"가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다" -> 최단거리들의 최대

즉, 육지내 각 위치에서 최단거리를 구한 다음 그 최단거리들의 최댓값을 출력해주면 되는 문제였습니다.

 

최단 거리를 구해야하기 때문에 너비 우선 탐색으로 구현하였습니다.

이중포문을 돌려 'L' , 육지일 때마다 bfs를 돌려 최단거리들을 구하고 최댓값을 구해주었습니다.

방문체크는 bfs를 돌릴때마다 초기화 시켜주었습니다.

 

 구현 코드

package BOJ.Gold;

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 B2589_보물섬 {
	static int R, C, MAX, cnt;
	static char[][] map;
	static int[][] deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static Queue<rc> bfs;
	static boolean[][] visit;
	static class rc {
		int r, c, d;

		public rc(int r, int c, int d) {
			super();
			this.r = r;
			this.c = c;
			this.d = d;
		}
	}
	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];
		visit = new boolean[R][C];
		bfs = new LinkedList<>();
		for (int r=0;r<R;r++) {
			String input = br.readLine();
			map[r] = input.toCharArray();
		}
		// 입력 완료
		MAX = Integer.MIN_VALUE;
		for (int r=0;r<R;r++) {
			for (int c=0;c<C;c++) {
				if (map[r][c]=='L') {
					visit[r][c] = true;
					bfs.offer(new rc(r, c, 0));
					bfsL(r, c);
					MAX = Math.max(MAX, cnt);
				}
			}
		}
		System.out.println(MAX);
	}
	
	static void bfsL(int r, int c) {
		while(!bfs.isEmpty()) {
			rc now = bfs.poll();
			for (int d=0;d<4;d++) {
				int nr = now.r+deltas[d][0];
				int nc = now.c+deltas[d][1];
				if (isIn(nr, nc)&&map[nr][nc] =='L' && visit[nr][nc]==false) {
					visit[nr][nc] = true;
					cnt = now.d+1;
					bfs.offer(new rc(nr, nc, now.d+1));
				}
			}
		}
		visit = new boolean[R][C]; // 방문체크 초기화
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

정답!