[BaekJoon] 2589 보물섬 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/2589

2.  문제

요약

• 보물섬 지도는 직사각형 모양이며 여러 칸으로 나뉘어져 있고 각 칸은 육지(L)나 바다(W)로 표시되어 있습니다.
• 이동은 상하좌우로 이웃한 육지로만 가능하고, 한 칸을 이동하는데에는 1시간이 걸립니다.
• 보물은 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 묻혀있고, 최단 거리로 이동하기 위해 같은 곳을 두 번 이상 지나가거나 멀리 돌아가서는 안됩니다.
• 보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 문제입니다.
• 입력: 첫 번째 줄에 50 이하의 자연수인 보물 지도의 세로, 가로 크기가 주어지고 두 번째 줄부터 L과 W로 표시된 보물 지도가 주어집니다.
• 출력: 첫 번째 줄에 보물이 묻혀있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int row, col;
	static char[][] map;
	boolean[][] visited;
	public int bfs(int x, int y) {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		Queue<Point> queue = new LinkedList<>();
		visited[x][y] = true;
		queue.offer(new Point(x, y, 0));
		int len = 0;
		while(!queue.isEmpty()) {
			Point cur_point = queue.poll();
			for(int i = 0; i < 4; i++) {
				int cx = cur_point.x + dx[i];
				int cy = cur_point.y + dy[i];
				if(cx >= 0 && cx < row && cy >= 0 && cy < col) {
					if(!visited[cx][cy] && map[cx][cy] == 'L') {
						visited[cx][cy] = true;
						queue.add(new Point(cx, cy, cur_point.len + 1));
						len = Math.max(len, cur_point.len + 1);
					}
				}
			}
		}
		return len;
	}
	
	public int getTime() {
		int max = Integer.MIN_VALUE;
		visited = new boolean[row][col];
		for(int i = 0; i < row; i++) {
			for(int j = 0; j < col; j++) {
				if(map[i][j] == 'L') {
					visited = new boolean[row][col];
					int len = bfs(i, j);
					max = Math.max(max, len);
				}
			}
		}
		return max;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		row = Integer.parseInt(input[0]);
		col = Integer.parseInt(input[1]);
		map = new char[row][col];
		for(int i = 0; i < row; i++) {
			String str = br.readLine();
			for(int j = 0; j < col; j++) {
				map[i][j] = str.charAt(j);
			}
		}
		br.close();
		Main m = new Main();
		bw.write(m.getTime() + "\n");
		bw.flush();
		bw.close();
	}
	
	public static class Point {
		int x, y, len;
		public Point(int x, int y, int len) {
			this.x = x;
			this.y = y;
			this.len = len;
		}
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• BFS 탐색을 진행할 때 해당 위치를 방문했는지 확인하기 위한 2차원 배열 visited를 생성합니다.
• 만약 현재 위치가 육지라면 BFS를 통해 현재 위치에서의 가장 긴 시간이 걸리는 최단 거리를 구합니다.
• 현재 위치에서 상하좌우 위치를 확인하여 해당 위치가 지도의 가로, 세로 크기 내에 위치하고 아직 방문되지 않았으며 육지라면 해당 위치를 탐색하기 위해 Queue에 집어넣고 현재까지 진행한 탐색에서의 최단 거리 최댓값과 현재 탐색하려고 Queue에 집어넣은 위치까지의 최단 거리를 비교하여 더 큰 값을 최단 거리 최댓값으로 합니다.
• BFS를 육지인 모든 위치에 대해서 진행하며 그 중 가장 큰 최단 거리가 해당 문제에서의 답이 됩니다.

1. 주어진 보물 지도 정보를 2차원 배열 map에 넣고 보물이 묻혀있는 두 곳 사이를 최단 거리로 이동하는 시간을 나타내는 변수인 max를 생성하고 정수의 최솟값으로 값을 초기화합니다.
2. 보물 지도의 전체 위치를 각각 반복문을 돌면서 해당 위치가 육지라면 BFS 알고리즘을 통해 해당 위치에서의 가장 긴 최단 거리를 이동하는 시간을 구합니다.
   1. BFS 탐색을 진행할 때 해당 위치를 방문했는지 확인하기 위해 2차원 배열 visited를 생성합니다.
   2. BFS 탐색을 통해 해당 위치에서의 가장 긴 최단 거리를 이동하는 시간을 구합니다.
      1. 상하좌우를 나타내는 1차원 배열 dx, dy를 생성합니다.
      2. BFS 탐색 시에 현재 탐색할 위치를 가져오기 위한 Queue를 생성합니다.
      3. 현재 위치는 방문하였으므로 현재 위치의 visited 값을 true로 변경하고 Queue에 현재 위치를 넣습니다.
      4. 현재 위치에서의 가장 긴 최단 거리를 이동하는 시간을 나타내는 변수인 len을 생성하고 값을 0으로 초기화합니다.
      5. Queue가 비워지기 전까지 반복문을 돌며 가장 긴 최단 거리를 이동하는 시간을 구합니다.
         1. Queue에서 현재 탐색할 위치를 뽑아 변수 cur_point에 넣습니다.
         2. 상하좌우 위치를 반복문을 돌면서 이후 탐색할 위치를 Queue에 넣고 그 때까지의 가장 긴 최단 거리를 이동하는 시간을 구합니다.
            1. 만약 현재의 위치가 보물 지도 내에 존재하고 아직 방문하지 않았으며 육지라면 해당 위치의 visited 값을 true로 변경하고 Queue에 해당 위치 및 해당 위치까지 이동하는 시간을 넣습니다.
            2. 현재의 len 값과 해당 위치까지 이동하는 데에 걸린 시간을 비교하여 더 긴 값을 len의 값으로 취합니다.
      6. 5번의 반복문이 끝난 후의 len 값을 반환합니다.
   3. 현재 위치에서의 가장 긴 최단 거리를 이동하는 시간을 변수 len에 넣습니다.
   4. 현재의 max 값과 len 값을 비교하여 더 큰 값을 max 값으로 취합니다.
3. 2번의 반복문이 끝난 뒤의 max 값이 보물이 묻혀있는 두 곳 사이를 최단 거리로 이동하는 시간이 되므로 해당 값을 출력합니다.