백준 2589번 <보물섬>

백준 알고리즘 2589번

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

2589번: 보물섬

---

2589번

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

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

---

문제 해결

BFS를 사용하여 문제를 풀이했다.

보물섬의 크기가 최대 50 * 50이기 때문에 보물섬에서 모든 육지를 기준으로 각 육지에서 가장 멀리 있는 육지를 찾았다.

 

BFS를 돌릴 때, 방문체크 배열을 int형 배열로 진행했는데, 이는 가장 멀리 있는 육지를 찾기 위함이었다.

생각해보니 굳이 int형 배열로 하지 않아도 되었던 것 같다. boolean형 배열로 방문체크를 진행하고 방문체크 후에 가장 멀리 있는 거리를 갱신해주는 식으로 해도 될 것 같다.

BFS

• 시작이 되는 육지를 기준으로 갈 수 있는 모든 육지까지를 탐색한다.
• 시작 육지를 방문 체크한 후에 Q에 넣는다.
• Q가 빌 때까지 다음과 같은 로직을 수행한다.
  • Q에서 꺼낸 위치의 인접 4방향 위치를 확인한다.
  • 이때, 보물섬을 벗어나거나, 바다인 경우는 방문할 수 없다. 또한 이미 방문한 경우라면 방문할 수 없다.
  • 방문할 수 있다면 해당 위치에 대해 방문 체크를 진행한 후 Q에 넣는다.
• 방문 체크 배열인 visit 배열에서 가장 큰 값이 시작 육지에서 가장 멀리 있는 육지까지의 최단 거리이다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class BOJ_2589 {
    static int N, M;
    static boolean[][] Map;
    static int[] di = {1, -1, 0, 0};
    static int[] dj = {0, 0, 1, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inArr = br.readLine().split(" ");
        N = Integer.parseInt(inArr[0]);
        M = Integer.parseInt(inArr[1]);
        Map = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if (chars[j] == 'L')
                    Map[i][j] = true;
            }
        }

        int answer = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (Map[i][j]) {
                    answer = Math.max(answer, BFS(new int[]{i, j}));
                }
            }
        }
        System.out.println(answer);
    }

    static int BFS(int[] start) {
        int[][] visit = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visit[i][j] = Integer.MAX_VALUE;
            }
        }

        Queue<int[]> Q = new ArrayDeque<>();
        Q.add(new int[]{start[0], start[1], 0});
        visit[start[0]][start[1]] = 0;
        while (!Q.isEmpty()) {
            int[] pop = Q.poll();
            for (int k = 0; k < 4; k++) {
                int ni = pop[0] + di[k];
                int nj = pop[1] + dj[k];
                if (ni < 0 || nj < 0 || ni >= N || nj >= M || !Map[ni][nj]) continue;
                if (visit[ni][nj] <= pop[2]+1) continue;
                visit[ni][nj] = pop[2] + 1;
                Q.add(new int[]{ni, nj, visit[ni][nj]});
            }
        }
        int answer = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visit[i][j] == Integer.MAX_VALUE) continue;
                answer = Math.max(answer, visit[i][j]);
            }
        }
        return answer;
    }
}

---

결과

 

---