[BAEKJOON] 2589. 보물섬(JAVA)

:D 문제

---

문제

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

 

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

 

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

입력

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

출력

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

Baekjoon

2589번: 보물섬

그래프 이론  브루트포스 알고리즘   그래프 탐색   너비 우선 탐색 

 

 

:D 풀이 방법

---

1. 보물이 묻혀 있는 곳 찾기(BFS)

문제에서는 육지(L)에서만 이동이 가능하다고 했기 때문에 현재 위치가 육지(L)인 경우에만 BFS탐색을 진행했다. 

각 Point에 인접한 육지를 탐색하면서 걸린 시간을 저장하고, 더 오래 걸리는 시간(time)을 찾아 갱신하였다.

그리고 인접한 모든 곳을 탐색했다면, 가장 오래 걸린 시간(time)을 리턴하였다.

private static int bfs(Point start) {

    // 시간 초기화
    int time = 0;

    // 시작 위치 큐에 저장
    Queue<Point> queue = new ArrayDeque<>();
    visited[start.x][start.y] = true;
    queue.add(start);

    while (!queue.isEmpty()) {

        Point current = queue.poll();

        // 4방 탐색
        for (int i = 0; i < 4; i++) {
            int nx = current.x + dirs[i][0];
            int ny = current.y + dirs[i][1];

            if (!isIn(nx, ny) || visited[nx][ny]) continue;

            // 육지라면
            if (map[nx][ny] == 'L') {

                // 한칸 이동한 것임으로 현재 위치에서 + 1
                queue.add(new Point(nx, ny, current.time + 1));
                visited[nx][ny] = true;
                time = Math.max(time, current.time + 1);
            }
        }
    }

    return time;
}

 

그리고 리턴한 값과 현재 저장된 값을 비교하여 더 큰 값으로 갱신해주었다.

int answer = 0;
// 모든 육지에 대해 bfs 탐색
for (int x = 0; x < N; x++) {
    for (int y = 0; y < M; y++) {

        // 바다라면 continue
        if (map[x][y] == 'W') continue;

        // 육지라면 탐색
        visited = new boolean[N][M]; // 초기화
        answer = Math.max(answer, bfs(new Point(x, y)));
    }
}

 

 

 

:D 작성 코드

---

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

public class Solution2589H {

    static class Point {
        int x, y;
        int time = 0;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Point(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }

    static int N, M;
    static char[][] map;
    static boolean[][] visited;
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상 - 하 - 좌 - 우

    public static void main(String[] args) throws IOException {

        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 생성
        map = new char[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            char[] line = br.readLine().toCharArray();
            map[i] = line;
        }

        int answer = 0;
        // 모든 육지에 대해 bfs 탐색
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < M; y++) {

                // 바다라면 continue
                if (map[x][y] == 'W') continue;

                // 육지라면 탐색
                visited = new boolean[N][M]; // 초기화
                answer = Math.max(answer, bfs(new Point(x, y)));
            }
        }
        System.out.print(answer);
    }

    private static int bfs(Point start) {

        // 시간 초기화
        int time = 0;

        // 시작 위치 큐에 저장
        Queue<Point> queue = new ArrayDeque<>();
        visited[start.x][start.y] = true;
        queue.add(start);

        while (!queue.isEmpty()) {

            Point current = queue.poll();

            // 4방 탐색
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dirs[i][0];
                int ny = current.y + dirs[i][1];

                if (!isIn(nx, ny) || visited[nx][ny]) continue;

                // 육지라면
                if (map[nx][ny] == 'L') {

                    // 한칸 이동한 것임으로 현재 위치에서 + 1
                    queue.add(new Point(nx, ny, current.time + 1));
                    visited[nx][ny] = true;
                    time = Math.max(time, current.time + 1);
                }
            }
        }

        return time;
    }

    // 범위 확인
    private static boolean isIn(int nx, int ny) {
        return nx >= 0 && ny >= 0 && nx < N && ny < M;
    }

    private static void print(char[][] arr) {
        for (char[] line : arr) {
            for (char c : line) {
                System.out.print(c + " ");
            }
            System.out.println();
        }
    }
}