[백준 2589] - 보물섬

문제

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

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

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

입력

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

출력

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

 

솔루션

• 최단 거리로 가는 가장 긴 시간이 걸리는 육지 두 곳에 보물이 있다고 하였다.
  • 하지만, 보물이 있는 곳을 단번에 알 수는 없다.
  • 따라서, 어느 한 육지 지점을 (L) 출발점으로 지정하여 BFS를 수행한 뒤, 가장 먼 길이를 추출한다.
  • 육지가 아닌 바다라면 BFS를 수행할 필요 없이 넘어가면 된다.
  • 이러한 과정을 지도의 모든 지점에 대해 수행하면 최종적으로 가장 멀면서 최단거리로 이동할 수 있는 시간이 나오게 되며, 이 값이 곧 답이 된다.

 

Code

• 전체코드 : Solution2589

public class Solution_2589 {
    static char[][] map;
    static int[][] dist;
    static boolean[][] visited;
    static int row, col;
 
    public static int Treasure_Hunt(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        int[] dx = { -1, 1, 0, 0 }, dy = { 0, 0, 1, -1 };
        int nx, ny, max = 0;
 
        visited[x][y] = true;
        dist[x][y] = 0;
        queue.offer(new Point(x, y));
 
        while (!queue.isEmpty()) {
            Point cur = queue.poll();
 
            for (int i = 0; i < 4; i++) {
                nx = dx[i] + cur.x;
                ny = dy[i] + cur.y;
 
                if (0 <= nx && nx < row && 0 <= ny && ny < col) {
                    if (!visited[nx][ny] && map[nx][ny] == 'L') {
                        queue.offer(new Point(nx, ny));
                        visited[nx][ny] = true;
                        dist[nx][ny] = dist[cur.x][cur.y] + 1;
                        max = Math.max(dist[nx][ny], max);
                    }
                }
            }
        }
 
        return max;
    }
    
 
    public static class Point {
        int x, y;
 
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

결과

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW
8