86. 보물섬 (백준 2589) [JAVA]

 

문제

문제 링크 : https://www.acmicpc.net/problem/2589

2589번: 보물섬

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	512MB	21331	7376	5341	37.898%

문제

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

입력

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

출력

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

풀이

처음에 보물의 좌표가 고정인 줄 알았는데, 갈 수 있는 두 곳이 가장 먼 거리였다.

그렇다면 결국 모든 육지 좌표에서 최단거리로 갔을 때 가장 먼 점을 찾아야 하므로,

BFS를 종료시점까지 수행하였을때를 가장 먼 거리로 놓고 모든 육지 좌표에서 수행하였다.

 

코드

import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static int M;
    static int[][] map;
    static int[] moveX = {0,0,1,-1};
    static int[] moveY = {1,-1,0,0};

    static int startX, startY;
    static int endX, endY;

    //둘간에 제일 먼 거리 -> 플로이드/와샬
    //상하좌우 이동을 플로이드 와샬 맵으로? -> 좌표가 너무 많음 (2500개)
    //그냥 모든 점에서 BFS 해보자
    //보물은 둘간에 제일 먼 거리

    public static void main(String[] args) throws IOException{
        StringTokenizer st;
        BufferedReader br = new java.io.BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        for(int i=0; i<N; i++){
            String[] s = br.readLine().replaceAll("L", "1").replaceAll("W", "0").split("");
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(s[j]);
            }
        }

        int answer = -1;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++) {
                if(map[i][j] == 1) {
                    answer = Math.max(answer, BFS(j,i));
                }
            }
        }

        System.out.println(answer);


    }
    public static int BFS(int x, int y) {
        int visited[][] = new int[N][M];
        Queue<point> q = new LinkedList<>();

        //initial setting
        visited[y][x] = 1;
        q.add(new point(x, y));
        int size, nextX, nextY;
        int round = 0;

        while(!q.isEmpty()) {
            size = q.size();
            for(int i=0; i<size; i++) {
                point cur = q.poll();

                for(int a =0; a<4; a++) {
                    nextX = cur.x + moveX[a];
                    nextY = cur.y + moveY[a];

                    if(nextX < 0 || nextX > M-1 || nextY <0 || nextY > N-1) continue;

                    //방문 안했고, 육지면 추가
                    if(visited[nextY][nextX] == 0 && map[nextY][nextX] == 1) {
                        q.add(new point(nextX, nextY));
                        visited[nextY][nextX] = 1;
                    }
                }                
            }
            round++;
        }
        return round-1;
    }
}

class point{
    int x;
    int y;

    public point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public void print() {
        System.out.println("y: " + y + " x: " + x);
    }
}

 

결과