[JAVA] 백준 2589 - 보물섬

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

N X M 지도가 주어지면, 보물의 위치의 최단거리를 구하는 문제이다. 근데 보물의 위치가 최장거리라서 사실 MAX값 구하기 문제이다.

N과 M의 크기가 50으로 작아서 완전탐색으로 BFS를 돌렸다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};

    static class Location {
        int i;
        int j;
        int dist = 0;

        Location(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        char[][] c = new char[info[0]][info[1]];
        for (int i = 0; i < info[0]; i++) {
            c[i] = br.readLine().toCharArray();
        }
        int max = -1;
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < c[0].length; j++) {
                if(c[i][j]=='L'){
                    boolean[][] visited = new boolean[info[0]][info[1]];
                    max = Math.max(max,bfs(i,j,c,visited));
                }
            }
        }
        System.out.println(max);
    }

    static int bfs(int i, int j, char[][] c, boolean[][] visited) {
        Location offer = new Location(i,j);
        Queue<Location> q = new LinkedList<>();
        q.offer(offer);
        int max = -1;
        while(!q.isEmpty()){
            Location poll = q.poll();
            if(visited[poll.i][poll.j])continue;
            visited[poll.i][poll.j] = true;
            max = Math.max(max,poll.dist);
            for (int k = 0; k < 4; k++) {
                int tx = poll.i+dx[k];
                int ty = poll.j+dy[k];
                if(check(tx,ty,c,visited)){
                    Location off = new Location(tx,ty);
                    off.dist = poll.dist+1;
                    q.offer(off);
                }
            }
        }
        return max;
    }

    static boolean check(int i, int j, char[][] c, boolean[][] visited) {
        if (i < 0 || i >= visited.length) return false;
        if (j < 0 || j >= visited[0].length) return false;
        if (visited[i][j]) return false;
        if (c[i][j] == 'W') return false;
        return true;
    }
    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

탐색문 안에 그냥 BFS함수를 풀어서 썼으면 메모리가 더 절약됐을 것 같다.

BFS 함수호출

BFS 반복문 내 구현

오히려 시간과 메모리가 늘었다. 

아래서부터 Q외부선언, Q외부선언 후 내부에서 Q.clear(), Q내부선언인데 함수로 호출하는게 빨랐다.

GPT는 GC때문이라고 하는데 재사용할수록 오히려 메모리 사용량이 커질수도 있다는 사실에 놀랐다.