[백준]2589: 보물섬 - JAVA

[백준]2589: 보물섬

www.acmicpc.net/problem/2589

2589번: 보물섬

풀이

최단거리 중에서의 최대값을 구하는 문제였다. BFS로 각 정점에서의 최단 거리를 구해주고 그 최단 거리 들 중의 최대값을 계산해 주었다.

 

BFS에서 현재 위치와 현재 위치 까지의 거리를 저장해줄 Node class를 만들어서 저장해 주었다. 

 

그리고 이중 for문으로 모든 노드를 확인하면서 '육지'인 경우에만 BFS탐색을 하도록 하였다.

 

코드

import java.util.*;
 
public class Main {    
    
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static char[][] board;
    static int n, m;
    static boolean[][] visited;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
        scan.nextLine();
        
        board = new char[n][m];
        for(int i = 0; i < n; i++) {
            String str = scan.nextLine();
            for(int j = 0; j < m; j++) {
                board[i][j] = str.charAt(j);
            }
        }
        
        int max = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == 'L') {
                    visited = new boolean[n][m];
                    int len = bfs(i, j);
                    max = Math.max(max, len);
                }
            }
        }
        System.out.println(max);
    }
    
    public static int bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y, 0));
        visited[x][y] = true;
        
        int len = 0;
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if(visited[nx][ny] == false && board[nx][ny] == 'L') {
                        q.offer(new Node(nx, ny, current.cost + 1));
                        len = Math.max(len, current.cost + 1);
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        return len;
    }
    
    public static class Node {
        int x;
        int y;
        int cost;
        
        public Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
    }
}