[백준/JAVA] 2589번: 보물섬

📖 문제

2589번: 보물섬

 

 

 

 

💡  풀이 방식

• BFS + 브루트포스

 

"모든 최단 거리 중 가장 긴 구간"

 

모든 육지(L)에서 BFS를 수행하며, 현재 육지에서 다른 위치까지의 가장 긴 시간이 걸리는 거리를 구한다.

그리고 그 거리를 정답과 비교해 더 큰 값으로 정답을 갱신한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N,M;
    static char[][] map;
    static boolean[][] visited;
    static int answer = 0;
    
    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];
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = str.charAt(j);
            }
        }
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(map[i][j] == 'L') {    // 💥 모든 육지에서 BFS 수행
                    visited = new boolean[N][M];
                    answer = Math.max(answer, bfs(i, j));
                }
            }
        }
        
        System.out.println(answer);
    }
    
    private static int bfs(int x, int y) {
        visited[x][y] = true;
        
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y, 0});
        
        int dist = 0;    // 육지 두 곳의 거리 중 최댓값
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= M)  continue;
                
                // 범위 내에 있고, 방문한 적 없는 육지인 경우
                if(!visited[nx][ny] && map[nx][ny] == 'L') {
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny, now[2] + 1});
                    dist = Math.max(dist, now[2] + 1);
                }
            }
        }
        
        return dist;
    }
}
 

 

 

---

💦 어려웠던 점

- 보물이 묻힌 곳을 구할 때, 가장 긴 시간이 걸리는 육지 두 곳을 어떻게 구하지?의 문제

 

 

🧐 새로 알게 된 내용

그냥 모든 육지에서 BFS를 수행하며 가장 긴 시간이 걸리는 육지 두 곳 간 거리를 찾으면 되는 것이었다.

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

#백준_2589 보물섬 - Java 자바

 

[BOJ - JAVA] 백준 2589: 보물섬