자바 : 백준 2589 / 보물섬

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

골드5

구현 방법

• 땅인 경우 bfs를 이용해서 최단 거리 기준 가장 먼 곳을 구한다.
• 이걸 모든 땅마다 반복하면서 가장 먼 곳을 구한다.

bfs를 이용한 이유

• 거리가 최단거리여야 하기 때문이다.
• dfs의 경우 최단 거리로 가지 않고 돌아갈 가능성이 존재한다.

그럼 bfs를 사용해서 답을 구할 순 없을까?

• 되긴 된다. 하지만 시간 초과가 발생한다. 즉, 너무 오래 걸려 비효율적이다.
• 왜냐하면 bfs는 기본적으로 모든 경로를 다 탐색하게 된다. 따라서 경로마다 거리가 나오는데 그 중 최솟값을 구한 뒤, bfs 탐색을 마치면, 그 중에서 최대 거리를 또 구해야 한다.
• bfs의 경우에는 “경로마다 거리가 나오는데 그 중 최솟값을 구함”을 안해도 된다.

코드

import java.util.*;
import java.io.*;

/**
 * 백준 2589
 * 보물섬
 * 골드5
 * https://www.acmicpc.net/problem/2589
 */
public class Boj2589 {

    private static int R, C;
    private static char[][] map;
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {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());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];

        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }

        int maxDistance = 0;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'L') {
                    maxDistance = Math.max(maxDistance, bfs(i, j));
                }
            }
        }

        System.out.println(maxDistance);
    }

    private static int bfs(int r, int c) {
        boolean[][] visited = new boolean[R][C];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{r, c, 0});
        visited[r][c] = true;

        int max = 0;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cr = cur[0], cc = cur[1], dist = cur[2];
            max = Math.max(max, dist);

            for (int i = 0; i < 4; i++) {
                int nr = cr + dr[i];
                int nc = cc + dc[i];

                if (nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc] || map[nr][nc] == 'W') {
                    continue;
                }

                visited[nr][nc] = true;
                q.offer(new int[]{nr, nc, dist + 1});
            }
        }

        return max;
    }
}

 

dfs라면?

package boj;

import java.io.*;
import java.util.*;

/**
 * 백준 2589 - 보물섬 (최단 거리 보장 DFS)
 */
public class Boj2589 {

    private static int R, C;
    private static char[][] map;
    private static int[][] distance; // 최단 거리 저장
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, -1, 0, 1};
    private static int maxDistance;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];

        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }

        maxDistance = 0;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'L') {
                    // 새로운 시작점마다 거리 배열 초기화
                    distance = new int[R][C];
                    for (int[] row : distance) {
                        Arrays.fill(row, Integer.MAX_VALUE);
                    }
                    distance[i][j] = 0; // 시작점 거리 0
                    dfs(i, j, 0);
                    distance[i][j] = Integer.MAX_VALUE;
                    for(int ii = 0; ii < R; ii++) {
                        for(int jj = 0; jj < C; jj++) {
                            if(distance[ii][jj] != Integer.MAX_VALUE)
                                maxDistance = Math.max(maxDistance, distance[ii][jj]);
                        }
                    }
                }
            }
        }

        System.out.println(maxDistance);
    }

    private static void dfs(int r, int c, int dist) {

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            // 지도 범위 내 && 육지('L')만 탐색
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && map[nr][nc] == 'L') {
                // 더 짧은 경로로 도달할 경우에만 탐색
                if (distance[nr][nc] > dist + 1) {
                    distance[nr][nc] = dist + 1;
                    dfs(nr, nc, dist + 1);
                }
            }
        }
    }
}

하지만 dfs는 시간초과!