[백준 2589] 보물섬 (자바)

백준 2589번 보물섬 (자바)

 

 

 

출처

www.acmicpc.net/problem/2589

2589번: 보물섬

 

 

 

문제

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

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

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

 

입출력 예

입출력 예 1

 

걸린 시간

문제 이해 잘못해서 헤맴ㅎㅎ

 

 

 

접근 방법

처음에 조건을 해당 위치에서 갈 수 있느냐 없느냐를 무시하고 가까운 거리를 찾은 후, 육지로 이어져 있으면  거리를 구하는 것으로 착각했다.

 

하지만 이 문제는 그런 조건은 필요 없고 그냥 일반 bfs처럼 해당 영역에서 기장 긴 거리를 구하고 동시에 시간도 구하면 되는 문제다.

 

나는 bfs를 사용하여 해당 구역에서 인접 육지를 쭈욱 탐색하도록 했다. 큐에서 맨 마지막에 나온 위치가 곧 제일 먼 위치이므로 매개변수로 가져온 좌표와 제일 먼 좌표를 이용하여 또 bfs를 사용해 시간을 탐색하도록 했다.

 

그런데 굳이 저처럼 bfs를 두 번 쓰지 않아도 한번 할 때 시간도 같이 계산하면 풀릴 것이라고 생각한다. (시간 복잡도가 많이 여유 있다.)

 

 

 

내 코드

	package dfsbfs;
	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 TreasureIsland {
	/**
	* 백준 2589 보물섬 (https://www.acmicpc.net/problem/2589)
	*/
	private static int row, col;
	private static char[][] map;
	private static boolean[][] visit;
	private static int time;
	private static int[] dx = {-1, 0, 1, 0};
	private static int[] dy = {0, 1, 0, -1};
	public static void main(String[] args) throws IOException {
	//육지 - L
	//바다 - W
	//상하좌우 이웃한 육지로만 이동 가능
	//한 칸 이동시 한 시간
	//보물 - 서로 최단거리, 가장 긴 시간이 걸리는 육지 두 곳
	//거리, 시간 두 개 구해야 함
	//같은 곳 한번만 가능
	//풀이
	//L마다 최단거리에 있는 L을 찾는다.
	//-> 이후, 시간을 구한다.
	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(reader.readLine());
	row = Integer.parseInt(st.nextToken());
	col = Integer.parseInt(st.nextToken());
	map = new char[row+1][col+1];
	visit = new boolean[row+1][col+1];
	for (int i=1; i<=row; i++) {
	char[] array = reader.readLine().toCharArray();
	for (int j=1; j<=col; j++) {
	map[i][j] = array[j-1];
	}
	}
	int result = 0;
	for (int i=1; i<=row; i++) {
	for (int j=1; j<=col; j++) {
	if (map[i][j] == 'L') {
	visit = new boolean[row+1][col+1];
	time = 0;
	bfs(i,j);//가까운 친구 찾기
	result = Math.max(result, time);
	}
	}
	}
	System.out.println(result);
	}//main
	private static void bfs(int x, int y) {
	Queue<Treasure> q = new LinkedList<>();
	q.add(new Treasure(x,y));
	visit[x][y] = true;
	int distance = Integer.MAX_VALUE;
	int targetX = 0, targetY = 0;
	while (!q.isEmpty()) {
	Treasure tres = q.remove();
	int qx = tres.x;
	int qy = tres.y;
	targetX = qx;
	targetY = qy;
	for (int i=0; i<4; i++) {
	int nx = qx + dx[i];
	int ny = qy + dy[i];
	if (nx<1 || ny<1 || nx>row || ny>col) {
	continue;
	}
	if (!visit[nx][ny] && map[nx][ny] == 'L') {
	visit[nx][ny] = true;
	q.add(new Treasure(nx, ny));
	}
	}
	}//while
	//최단거리, 최대시간
	//distance 보다 거리가 같거나 가까운 경우 갱신
	time = Math.max(time, calTime(x, y, targetX, targetY));//시간계산
	}//bfs
	private static int calTime(int x, int y, int targetX, int targetY) {
	Queue<Treasure> q = new LinkedList<>();
	boolean[][] timeVisit = new boolean[row+1][col+1];
	q.add(new Treasure(x,y,0));
	timeVisit[x][y] = true;
	int result = 0;
	while (!q.isEmpty()) {
	Treasure t = q.remove();
	int qx = t.x;
	int qy = t.y;
	int qt = t.time;
	if (qx == targetX && qy == targetY) {
	result = qt;
	break;
	}
	for (int i=0; i<dx.length; i++) {
	int nx = qx + dx[i];
	int ny = qy + dy[i];
	if (nx < 1 || ny < 1 || nx > row || ny > col) {
	continue;
	}
	if (!timeVisit[nx][ny] && map[nx][ny] == 'L') {
	timeVisit[nx][ny] = true;
	q.add(new Treasure(nx,ny,qt+1));
	}
	}
	}//while
	return result;
	}//calTime
	static class Treasure {
	int x, y, time;
	Treasure (int x, int y) {
	this.x = x;
	this.y = y;
	}
	Treasure (int x, int y, int time) {
	this.x = x;
	this.y = y;
	this.time = time;
	}
	}
	}

view raw TreasureIsland.java hosted with ❤ by GitHub

 

 

고려할 점

1. bfs 사용할 것

2. 시간 구할 것