백준 2589번 보물섬 :: 마이구미

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

private void solve() {
    int c = sc.nextInt();
    int r = sc.nextInt();
    char[][] map = new char[c][r];
    int[] dx = { -1, 0, 1, 0 };
    int[] dy = { 0, -1, 0, 1 };
    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 (0 <= nx && nx < r && 0 <= 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;
    }
}