백준 2589 자바

<문제>

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

2589번: 보물섬

<설명>

맨 처음 문제를 접근할 때는 보물이 묻혀 있는 2곳을 잡는 기능과 해당 보물이 묻혀 있을 때, 최단 거리를 구하는 기능으로 하면 구할 수 있다고 생각했다. 

그러나 생각해보니 bfs로 탐색할 경우 첫 위치부터 갈 수 있는 거리까지 탐색을 하기 때문에 보물이 묻혀 있는 건 신경 안 써도 된다고 생각이 들었다. 

 

이중 for문을 이용해서 육지인지 확인하고, 방문한 곳인지 확인을 한다. 둘다 해당사항이 존재하지 않으면, bfs에서 탐색을 시작해서 갈 수 있는 최대 길이를 구하면 된다. 

 

원래는 Queue 내에 배열을 넣어서 x, y를 가지고 구하려고 했으나, 첫 시작부터 이동했던 거리를 체크해야 하기 때문에 Node라는 클래스를 만들어서 x, y와 거리까지 Node 클래스에 저장했다.

 

<코드>

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


public class Main {

    public static int n;
    public static int m;
    public static char[][]map;
    public static boolean visited[][];
    public static int[] dx = {-1,1,0,0};
    public static int[] dy = {0,0,-1,1};

    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];
        visited = new boolean[n][m];

        for(int i = 0; i < n; i++) {
            String s = br.readLine();
            for(int j = 0; j < m; j++) {
                map[i][j] = s.charAt(j);
            }
        }
        int resultDistance = 0;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(map[i][j] == 'L') {
                    visited = new boolean[n][m];
                    visited[i][j] = true; 
                    int result = bfs(i,j);
                    resultDistance = Math.max(result,resultDistance);
                }
            }
        }
        System.out.println(resultDistance);
    }

    public static int bfs(int x, int y) {
        int result = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(x,y,0));
        while(!queue.isEmpty()) {
            Node now = queue.poll();
            int nowX = now.x;
            int nowY = now.y;

            for(int i = 0; i < 4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];
                if(nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) continue;
                if(!visited[nextX][nextY] && map[nextX][nextY] == 'L') {
                    visited[nextX][nextY] = true;
                    queue.add(new Node(nextX, nextY, now.distance+1));
                    result = Math.max(result, now.distance + 1);
                }
            }
        }
        return result;
    }
    public static class Node {
        public int x;
        public int y;
        public int distance;
        public Node(int x, int y, int distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }

    }
}