[Java] 백준 2589번 : 보물섬

문제

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

예제 입력 1

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

예제 출력 1

8

 

소스코드

import java.awt.Point;
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 Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int R, C, maxVal=0, result=0;
	private static char [][] map;
	private static int [] dx = {-1,1,0,0};
	private static int [] dy = {0,0,-1,1};
	private static int [][] visited;
	
	public static void main(String[] args) throws IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(bf.readLine());
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		map=new char[R][C];
		visited=new int[R][C];
		
		for(int r=0;r<R;r++) {
			st=new StringTokenizer(bf.readLine());
			map[r]=st.nextToken().toCharArray();
		}
		
		for(int r=0;r<R;r++) {
			for(int c=0;c<C;c++) {
				if(map[r][c]=='L') {	// 육지인 경우 가능한 최소 시간을 탐색함
					visited=new int[R][C];	// (r, c)에서부터 걸리는 시간을 저장할 배열
					maxVal=0;	// (r, c)에서의 최댓값
					bfs(r, c);	// 최단 경로 시간 탐색
					result=Math.max(result, maxVal);	// 탐색한 시간이 현재까지의 시간보다 크면 result 값 갱신
				}
			}
		}
		System.out.println(result-1);
	}

	public static void bfs(int r, int c) {
		Queue<Point> queue=new LinkedList<>();
		queue.offer(new Point(r, c));
		
		visited[r][c]=1;
		
		while(!queue.isEmpty()) {
			Point p=queue.poll();
			
			for(int i=0;i<4;i++) {
				int nx=p.x+dx[i];
				int ny=p.y+dy[i];
				
				if(isIn(nx, ny) && visited[nx][ny]==0 && map[nx][ny]=='L') {
					visited[nx][ny]=visited[p.x][p.y]+1;	// bfs 탐색할 때마다 이전 위치의 시간에 1을 더해줌
					maxVal=Math.max(maxVal, visited[nx][ny]);
					queue.add(new Point(nx, ny));
				}
			}
		}	
	}
	
	
	public static boolean isIn(int r, int c) {
		return r>=0 && r<R && c>=0 && c<C;
	}
}