[BOJ] 보물섬

문제

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

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

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

제한사항

이외의 제한사항은 없다.

첫번째 생각

BFS탐색을 통해 가장 L과 L 사이의 가장 긴 거리를 찾으면 되는 문제이다.

Code

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

public class Main {
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int col = sc.nextInt();
		int row = sc.nextInt();
		int ans = 0;
		sc.nextLine();
		char[][] map = new char[col][row];
		for(int y=0; y<col; y++) {
			map[y] = sc.nextLine().toCharArray();
		}
		Queue<Point> q;
		boolean[][] visit;
		for(int y=0; y<col; y++) {
			for(int x=0; x<row; x++) {
				if ( map[y][x] == 'L') {
					q = new LinkedList<Point>();
					visit = new boolean[col][row];
					q.add(new Point(x,y,0));
					while(!q.isEmpty()) {
						Point p = q.poll();
						if ( ans < p.D ) ans = p.D;
						visit[p.Y][p.X] = true;
						for(int dir=0; dir<4; dir++) {
							int tempX = p.X+dx[dir];
							int tempY = p.Y+dy[dir];
							if ( tempX >= 0 && tempY >= 0 && tempX < row && tempY < col ) {
								if(map[tempY][tempX] == 'L' && !visit[tempY][tempX] ) {
									visit[tempY][tempX] = true;
									q.add(new Point(tempX,tempY,p.D+1));
								}
							}
						}
					}
				}
			}
		}
		System.out.println(ans);
		
		
	}
	
	public static class Point {
		int X;
		int Y;
		int D;
		Point(int x,int y,int d) {
			X=x;
			Y=y;
			D=d;
		}
	}
}