[백준] 2589 보물섬 (JAVA)

문제링크:

2589번: 보물섬

 

 

문제:

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

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

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

 

 

입력:

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

 

 

출력:

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

 

 

문제 이해:

이 문제는 두개의 육지 안에 보물이 숨겨져 있다.

보물이 숨겨져 있는 위치는 두 육지간의 최단경로가 제일 긴 부분에 있다. 즉 다음과 같은 것이다.

결국 육지와 바다로 구성되어있는 행렬이 주어졌을때 최단경로가 가장 긴 두 육지의 길이를 출력하는 것이 문제이다.

 

 

구현 방향:

이를 구현하기 위해서는 각 육지 칸을 시작점으로 삼아 BFS를 수행하고, 해당 지점에서 도달할 수 있는 다른 모든 육지까지의 최단 거리를 계산해야 한다. 이렇게 각 육지에서 얻은 최단 거리들 중 최댓값을 기록해 두면, 최종적으로는 전체 육지 쌍 중 최장 최단 경로(가장 먼 두 지점 간 거리)를 구할 수 있는 것이다. 

 

이를 코드로 그대로 구현하면 다음과 같다.

 

정답코드:

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 {
    static char[][] matrix;
    static int N,M;
    static boolean[][] visited;
    static int maxResult=0;


    public static void bfs(int startX, int startY){
        Queue<int[]> q = new LinkedList<>();
        int[][] dist = new int[N][M];
        boolean[][] visited = new boolean[N][M];

        int sx = startX, sy = startY;

        // 방문/거리 초기화
        q.add(new int[]{sx, sy});
        visited[sx][sy] = true;
        dist[sx][sy] = 0;

        while (!q.isEmpty()){
            int[] cur = q.poll();
            int curX = cur[0];
            int curY = cur[1];


            // 상
            if (curX > 0 && !visited[curX-1][curY] && matrix[curX-1][curY] == 'L') {
                visited[curX-1][curY] = true;
                dist[curX-1][curY] = dist[curX][curY] + 1;
                q.add(new int[]{curX-1, curY});
                if(maxResult<dist[curX-1][curY]) maxResult=dist[curX-1][curY];
            }
            // 하
            if (curX + 1 < N && !visited[curX+1][curY] && matrix[curX+1][curY] == 'L') {
                visited[curX+1][curY] = true;
                dist[curX+1][curY] = dist[curX][curY] + 1;
                q.add(new int[]{curX+1, curY});
                if(maxResult<dist[curX+1][curY]) maxResult=dist[curX+1][curY];
            }
            // 좌
            if (curY > 0 && !visited[curX][curY-1] && matrix[curX][curY-1] == 'L') {
                visited[curX][curY-1] = true;
                dist[curX][curY-1] = dist[curX][curY] + 1;
                q.add(new int[]{curX, curY-1});
                if(maxResult<dist[curX][curY-1]) maxResult=dist[curX][curY-1];
            }
            // 우
            if (curY + 1 < M && !visited[curX][curY+1] && matrix[curX][curY+1] == 'L') {
                visited[curX][curY+1] = true;
                dist[curX][curY+1] = dist[curX][curY] + 1;
                q.add(new int[]{curX, curY+1});
                if(maxResult<dist[curX][curY+1]) maxResult=dist[curX][curY+1];
            }
        }
    }


    public static void main(String[] args) throws IOException {
        //초기 입력 세팅
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());

        matrix=new char[N][M];
        visited=new boolean[N][M];

        for (int i=0; i<N; i++){
            StringBuilder sb= new StringBuilder(br.readLine());
            for (int j=0; j<M; j++){
                matrix[i][j]=sb.charAt(j);
            }
        }
        //세팅 끝

        //육지지역에서 탐색 시작
        for (int i=0; i<N; i++){
            for (int j=0; j<M; j++){
                if(matrix[i][j]=='L'){
                    bfs(i,j);
                }
            }
        }

        //결과 출력
        System.out.println(maxResult);

    }
}

 

 

마무리하며:

정리하면, 각 육지에서 BFS를 돌려 다른 육지까지의 최단 거리를 구하고, 그 중 가장 긴 값을 답으로 선택하는 방식이다. 이렇게 하면 보물이 숨겨진 위치를 찾을 수 있다는 문제의 요구사항을 충족할 수 있다.

 

감사합니다.