[자바] 백준 2589 : 보물섬 / BFS 풀이

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

2589번: 보물섬

골드5 난이도, 정답률 37% 문제입니다.

개인적으로 잘 만든 BFS문제라고 생각이 듭니다.

---

문제 이해 및 분석

이 문제는 요구 사항을 이해하기 조금 어려웠습니다.

​

문제에서 보물이 묻힌 두 곳의 최단 거리를 구하라고 했는데,

일단 여기서 보물이 묻힌 두 곳은 어떻게 구해야하는지가 중요합니다.

​

보물이 묻힌 두 곳은 육지에서 서로 가장 먼 곳에 각각 묻혀있습니다.

만약 육지인 (a,b) 좌표와 (a1, b1) 좌표까지의 거리가 가장 멀다면 (a,b)와 (a1,b1)에는 보물이 묻힌 곳이고 이 둘 사이의 최단 거리를 출력하면 되는 문제입니다.

​

예시를 보면서 다시 한 번 이해해보겠습니다.

 

위에서 색칠된 L은 보물이 묻힌 곳을 의미합니다.

육지상 가장 먼 곳에 보물이 각각 있다고 명시되어 있죠? 위에 그림을 보면 육지는 섬 형태로 총 2개가 있습니다.

​

왼쪽 육지에 보물이 있을 수도 있고, 오른쪽 육지에 보물이 있을 수도 있습니다.

보물은 최장거리에 묻혀져 있으니 우리가 직접 손으로 육지에서의 가장 먼 곳의 거리를 세어봅시다.

​

왼쪽 섬에는 색칠된 L끼리의 거리를 손으로 세어본다면 8칸을 가야합니다.

오른쪽 섬에는 보물이 묻힐 수 있는 최장거리를 손으로 세어 본다면 7칸이 됩니다. (6, 0) -> (6,4)

​

따라서 왼쪽 섬에 보물이 있음을 알 수 있고, 8칸이 정답임을 우리는 알 수 있습니다.

​

​

그렇다면 문제를 풀기 위해서 어떤 알고리즘을 써야할까요?

우리의 직관을 컴퓨터적인 사고로 바꿔봅시다.

L(육지)을 탐색하면서 각각의 육지에서 가장 먼 곳의 최단 거리를 구해야합니다.

​

결국에 완전 탐색을 수행하면서 이를 직접 구해줘야합니다.

또한 최단 거리라는 말이 제시되어 있으니 DFS가 아닌 BFS로 탐색을 해야함을 알 수 있습니다.

​

또한 섬 사이의 최단 거리를 구해야하므로 BFS를 수행하면서, 다음 칸으로 이동할 때 이전 칸 + 1을 해주면서 최단 거리를 구해보도록 하겠습니다.

​

이 포인트들만 찾는다면 문제는 쉽게 풀 수 있습니다.

 

 

문제 풀이

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    private static final Scanner sc = new Scanner(System.in);
    private static int n, m;
    private static char[][] map;
    private static boolean[][] visited;
    private static int[][] pos = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    private static int[][] distance;
    private static List<Integer> oneOfAnswer = new ArrayList<>();

    public static void main(String[] args) {
        initData();
        findAnswer();
        System.out.println(Collections.max(oneOfAnswer));
    }

    private static void initData() {
        n = sc.nextInt();
        m = sc.nextInt();

        map = new char[n][m];
        visited = new boolean[n][m];
        distance = new int[n][m];

        for (int i = 0; i < n; i++) {
            String str = sc.next();
            map[i] = str.toCharArray();
        }
    }

    private static void findAnswer() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'L') {
                    bfs(i, j);
                    initNextStep();
                }
            }
        }
    }

    private static void bfs(int row, int col) {
        Queue<int[]> queue = new LinkedList<>();
        visited[row][col] = true;
        queue.add(new int[]{row, col});

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            for (int i = 0; i < pos.length; i++) {
                int nr = now[0] + pos[i][0];
                int nc = now[1] + pos[i][1];

                if (canUseBfs(nr, nc)) {
                    visited[nr][nc] = true;
                    distance[nr][nc] = distance[now[0]][now[1]] + 1;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
        addMaxDistance(distance);
    }

    private static boolean canUseBfs(int nr, int nc) {
        return nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc] && map[nr][nc] == 'L';
    }

    private static void addMaxDistance(int[][] mapOfDistance) {
        int maxValueOfDistance = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                maxValueOfDistance = Math.max(maxValueOfDistance, mapOfDistance[i][j]);
            }
        }
        oneOfAnswer.add(maxValueOfDistance);
    }

    private static void initNextStep() {
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited[i], false);
            Arrays.fill(distance[i], 0);
        }
    }
}