[Java, 자바] 백준 2589번, 보물섬(BFS)

백준 2589번

👉🏻 https://www.acmicpc.net/submit/2589

# 난이도 : 골드5

---

문제내용

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

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

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

---

입력

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

---

출력

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

---

풀이방법

기존 최단거리를 구하는 문제와 달리 가장 긴 구간을 구해줘야 되는 문제더라구요 !

기존 BFS, DFS로 탐색을 진행할 때 입력 받은 2차원 배열에 조건에 맞는 데이터와 방문 배열을 방문하지 않았을 때만 BFS를 호출했다면 해당 문제는 최장 거리를 구해야되기 때문에 방문 배열에 방문하지 않았을 때의 조건을 포함하지 않고 BFS를 호출하기 전 방문 배열을 지속적으로 초기화해 주었습니다.

큐에 좌표을 넣을 때 누적 이동 값을 같이 넣어준 이후 누적 값을 지속적으로 비교한 뒤 BFS 메서드를 return하였을 때 최대 크기를 계속 초기화해주어 문제를 해결하였습니다 :)

---

코드

import java.util.*;

public class Main{

    static int n, m, answer;
    static String[][] arr;
    static boolean[][] visit;
    static int[] mx = {0, 0, 1, -1};
    static int[] my = {1, -1, 0, 0};
    static Queue<int[]> Q;

    public static int BFS(int x, int y){
        Q = new LinkedList<>();
        visit[x][y] = true;
        Q.offer(new int[]{x, y, 0});
        int result = Integer.MIN_VALUE;
        while(!Q.isEmpty()){
            int[] ca = Q.poll();
            result = Math.max(ca[2], result);
            for(int i = 0; i < 4; i++){
                int nx = ca[0] + mx[i];
                int ny = ca[1] + my[i];
                if(nx >= 0 && ny >= 0 && nx < n && ny < m){
                    if(!visit[nx][ny]&& arr[nx][ny].equals("L")){
                        visit[nx][ny] = true;
                        Q.offer(new int[]{nx, ny, ca[2] + 1});
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new String[n][m];

        for(int i = 0; i < n; i++){
            String[] str = scan.next().split("");
            for(int j = 0; j < m; j++){
                arr[i][j] = str[j];
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(arr[i][j].equals("L")){
                    visit = new boolean[n][m];
                    int result = BFS(i, j);
                    answer = Math.max(answer, result);
                }
            }
        }
        System.out.println(answer);
    }
}