보물섬 - 백준 2589

문제 링크

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

문제 풀이

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 문제이다.

 

최단 거리에 대한 조건은 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳이라고 명시되어 있다.

이 말은 최단 거리들 중에서 가장 시간이 오래 걸리는 두 점을 찾으라는 말이며 위치로 본다면 최단 거리들 중에서 가장 먼 거리를 구하라는 말이다.

 

문제에서 최단 거리들 중에서 가장 시간이 오래 걸린다는 말은 두 점 간의 최단 거리는 여러 개가 존재할 수 있고 그 중에서 가장 거리가 먼 두 점을 찾으라는 말로 해석하면 된다.

 

예시

그림을 통해 지도 내 존재하는 어떤 한 점에서 다른 점까지의 최단 거리들의 존재를 확인할 수 있다.

 

파란색 점들은 시작 점에서 이동할 수 있는 지점들이며 그 중에 최대한 먼 거리가 또 다른 주황색 점이다.

코드

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 {
    private static int rowSize;
    private static int colSize;
    private static int[][] map;
    private static int[] dx = new int[]{0, 0, 1, -1};
    private static int[] dy = new int[]{1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        rowSize = Integer.parseInt(st.nextToken());
        colSize = Integer.parseInt(st.nextToken());
        map = new int[rowSize][colSize];

        for (int i = 0; i < rowSize; i++) {
            String[] row = br.readLine().split("");
            for (int j = 0; j < colSize; j++) {
                String value = row[j];
                if (value.equals("L")) {
                    map[i][j] = 1;
                }
            }
        }
        int answer = 0;
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                if (map[i][j] == 1) {
                    boolean[][] visited = new boolean[rowSize][colSize];
                    int maxDistance = search(i, j, visited);
                    answer = Math.max(maxDistance, answer);
                }
            }
        }
        System.out.println(answer);
        br.close();
    }

    public static int search(int row, int col, boolean[][] visited) {
        Queue<Coordinate> queue = new LinkedList<>();
        queue.offer(new Coordinate(row, col,0));
        visited[row][col] = true;
        int maxDist = 0;
        while (!queue.isEmpty()) {
            Coordinate current = queue.poll();

            if(maxDist < current.getDist()){
                maxDist = current.getDist();
            }
            for (int i = 0; i < 4; i++) {
                int nRow = current.getRow() + dx[i];
                int nCol = current.getCol() + dy[i];

                if(isIn(nRow, nCol) && map[nRow][nCol]==1 && !visited[nRow][nCol] ){
                    visited[nRow][nCol] = true;
                    queue.offer(new Coordinate(nRow, nCol, current.getDist()+1));
                }
            }
        }
        return maxDist;
    }

    private static boolean isIn(int row, int col) {
        return (0 <= row && row < rowSize) && (0 <= col && col < colSize);
    }
}

class Coordinate {
    private final int row;
    private final int col;
    private final int dist;
    public Coordinate(int row, int col, int dist) {
        this.row = row;
        this.col = col;
        this.dist = dist;
    }

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public int getDist() {
        return dist;
    }