• 백준 2589번 보물섬 :: 마이구미
    알고리즘 풀이/그래프 2018. 1. 28. 18:05
    반응형

    이 글은 백준 알고리즘 문제 2589번 "보물섬" 을 풀이한다.

    풀이 방법으로는 BFS(너비 우선 탐색) 을 이용한다.

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

    BFS - http://mygumi.tistory.com/102


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

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

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


    문제는 보물이 묻힌 두 곳 간의 최단 거리를 구해야한다.

    문제에서 얻을 수 있는 정보는 다음과 같다.


    • 하나의 연결된 육지를 기준으로 보물이 두 곳에 묻혀있다.
    • 육지에서 서로 가장 멀리 떨어져있는 두군데가 보물이 묻혀있는 곳이 된다.


    하나의 연결된 육지에서 가장 멀리 떨어져있는 두 곳을 찾아야한다.

    일반적으로 DFS, BFS 와 같은 탐색 문제는 연결된 곳 중 하나를 기준으로 탐색한다.

    하지만 이 문제에서는 연결된 육지 하나하나를 기준으로 탐색한다.


    예를 들어, 하나의 육지를 기준으로 BFS 의 경우의 문제를 확인하면 이해할 수 있을 것이다.


    2589번 보물섬


    위처럼 BFS 할 경우, 연결된 육지에서의 가장 멀리 떨어진 곳의 시간은 최단 시간이 아니다.

    최단 시간의 경로는 다음과 같다.


    2589번 보물섬


    위와 같은 경우가 존재하기 때문에,  탐색은 연결된 각 육지를 기준으로 하게 된다.

    일반적인 BFS 문제와 다를 게 없이, 탐색하는 기준만 달라졌을 뿐이다.


    Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2005/2589.java


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    private void solve() {
        int c = sc.nextInt();
        int r = sc.nextInt();
        char[][] map = new char[c][r];
        int[] dx = { -101};
        int[] dy = { 0-10};
        int ans = 0;
     
        for (int i = 0; i < c; i++) {
            map[i] = sc.readLine().toCharArray();
        }
     
        for (int i = 0; i < c; i++) {
            for (int j = 0; j < r; j++) {
                Queue<Point> q = new LinkedList<Point>();
                boolean[][] visited = new boolean[c][r];
                int[][] dist = new int[c][r];
                char ch = map[i][j];
                visited[i][j] = true;
                q.add(new Point(i, j));
                int temp = 0;
     
                while (!q.isEmpty()) {
                    Point p = q.poll();
                    int x = p.x;
                    int y = p.y;
     
                    for (int k = 0; k < 4; k++) {
                        int nx = dx[k] + x;
                        int ny = dy[k] + y;
     
                        if (<= nx && nx < r && <= ny && ny < c) {
                            if (!visited[ny][nx] && map[ny][nx] == ch) {
                                q.add(new Point(ny, nx));
                                dist[ny][nx] = dist[y][x] + 1;
                                visited[ny][nx] = true;
     
                                if (temp < dist[ny][nx]) {
                                    temp = dist[ny][nx];
                                }
                            }
                        }
                    }
                }
                if (ans < temp) {
                    ans = temp;
                }
            }
        }
        System.out.println(ans);
    }
     
    public static class Point {
        int x;
        int y;
     
        Point(int y, int x) {
            this.x = x;
            this.y = y;
        }
    }
    cs


    반응형

    댓글

Designed by Tistory.