[알고리즘 PS] 2589번 보물섬 자바 문제풀이

문제

해당 포스팅은 백준의 2589번 보물섬 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

2589번: 보물섬

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이번 문제는 BFS 로 해결할 수 있는 문제였다.

 

골드 5라고 하는데 막상 풀면 실버 1? 정도 느낌의 문제였다.

 

해결법

 

각각 배열을 돌며 L일 때 BFS 로 갈 수 있는 최대 길이를 매번 갱신해주면 된다.

 

주의해야할 점이 배열을 한 번씩 다 돌면 시간 초과가 나오기 때문에 L 인 것만 돌아야 한다.

 

정답 코드

public class Main {

    private static int l;
    private static int w;
    private static String[][] arr;
    private static int[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] lw = br.readLine().split(" ");

        l = Integer.parseInt(lw[0]);
        w = Integer.parseInt(lw[1]);

        arr = new String[l][w];

        for (int i = 0; i < l; i++) {
            String[] s = br.readLine().split("");
            for (int j = 0; j < w; j++) {
                arr[i][j] = s[j];
            }
        }

        int max = 0;

        for (int i = 0; i < l; i++) {
            for (int j = 0; j < w; j++) {
                if(arr[i][j].equals("L")) {
                    visited = new int[l][w];
                    max = Math.max(max, getTreasure(j, i));   
                }
            }
        }

        bw.write(String.valueOf(max - 1));

        bw.flush();
        bw.close();
    }

    private static int getTreasure(int x, int y) {

        int[] xPos = {1, -1, 0, 0};
        int[] yPos = {0, 0, 1, -1};

        Queue<Pair> queue = new LinkedList<>();

        queue.add(new Pair(x, y));
        visited[y][x] = 1;

        while(!queue.isEmpty()) {
            Pair front = queue.remove();

            for (int i = 0; i < 4; i++) {
                int xx = front.x + xPos[i];
                int yy = front.y + yPos[i];

                if(!(0 <= xx && xx < w && 0 <= yy && yy < l)) continue;
                if(visited[yy][xx] != 0) continue;
                if(arr[yy][xx].equals("W")) continue;

                visited[yy][xx] = visited[front.y][front.x] + 1;
                queue.add(new Pair(xx, yy));
            }
        }

        int max = 0;

        for (int i = 0; i < visited.length; i++) {
            for (int j = 0; j < visited[i].length; j++) {
                max = Math.max(max, visited[i][j]);
            }
        }

        return max;
    }

    private static class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.