[백준 Gold 5] 2589 보물섬 - Java

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

2589번: 보물섬

 

접근 과정 : 

• 임의의 육지 2개를 고르고, 그 사이의 최단거리가 가장 긴 거리를 탐색하는 문제이다.
• 육지 하나하나 모두 BFS 해서 최장 거리를 탐색하는 완전탐색 방법으로 풀이할 수 있다.

 

• ++ 한 번 거리가 측정된 경로는 다시 탐색하지 않고 사용하는 것이 시간을 줄일 수 있는 포인트..
• 이 부분에 대해서는 좀 더 고민이 필요하다.

 

소스 코드 및 결과 :

 

package BOJ;

/* 
    보물섬
*/

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

public class BOJ2589 {

    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();
        }

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

        System.out.println(distance);

    }

    static int R, C, distance;
    static char[][] map;
    static int[][] visit;
    static int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    static int BFS(int r, int c) {

        visit = new int[R][C];

        int d = 0;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] { r, c });
        visit[r][c] = 1;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();

            d = Math.max(d, visit[now[0]][now[1]]);

            for (int i = 0; i < 4; i++) {
                int nr = now[0] + move[i][0];
                int nc = now[1] + move[i][1];

                if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
                    continue;
                }

                if (map[nr][nc] == 'W' || visit[nr][nc] != 0) {
                    continue;
                }

                visit[nr][nc] = visit[now[0]][now[1]] + 1;
                queue.add(new int[] { nr, nc });

            }
        }

        return d-1;
    }

}

 

P.S 

다른 백준 코드를 보니, 확실히 시간이 짧은 코드들이 여럿 있더라..

근데 나는 아직 그렇게는 못 풀것 같다..

해당 문제에 대해서는 좀 더 고민이 필요하다.