[백준] 2589번 : 보물섬

2589번: 보물섬

---

[BFS]

개인적으로 브루트 포스 방법을 좋아하지 않는다. 문제에서 정점은 최대 50x50 = 2500개라서 브루트 포스를 해도 시간이나 메모리적으로 촉박하진 않지만, 다른 방법으로 풀어보고 싶었다. 그래서 주어진 map에서 'L'이면 주변의 'L'이 몇 개인지 세어 우선순위 큐에 좌표(i, j)를 넣었고, 주변에 'L'이 가장 적은 좌표부터 꺼내어 BFS를 하며 거리를 측정하였다. 그러나 이 방법에는 치명적인 오류가 있었다.

W	L	W	L
W	L	L	L
L	L	L	L
L	L	L	L

위와 같은 표가 있을 떄, 가장 먼 정점은 (4, 1)과 (1, 4)이다. 하지만 우선순위 큐에서 가장 먼저 나오는 정점은 (1, 2)가 될 수도, (1, 4)가 될 수도 있다. 우선순위 큐는 넣은 순서대로 나오는 것이 아니기 때문에, 그때그때 값이 달라질 수 있기 때문에 정답이라고 볼 수 없다.

 

그래서 결국 'L'인 모든 정점에 대해 BFS를 실시했고, 가장 값이 클 때만 기록해 답으로 제출했다.

# Code </>

public class Main {

    static class Point{
        int y, x, d;
        public Point(int yy, int xx, int dist){
            y=yy;
            x=xx;
            d = dist;
        }
    }
    static char[][] map = new char[51][51];
    static boolean[][] visit;

    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static int n, m, max = 0;

    static void BFS(){

        Queue<Point> Q = new LinkedList<>();

        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++){
                visit = new boolean[51][51];

                if(map[i][j] == 'L'){
                    visit[i][j] = true;
                    Q.add(new Point(i, j, 0));
                }

                while(!Q.isEmpty()){
                    Point p_ = Q.poll();
                    int y = p_.y;
                    int x = p_.x;
                    int d = p_.d;

                    for(int a=0; a<4; a++) {
                        int ny = y + Y[a];
                        int nx = x + X[a];
                        if (ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx] || map[ny][nx] == 'W') continue;
                        visit[ny][nx] = true;

                        max = Math.max(d+1, max);
                        Q.add(new Point(ny, nx, d + 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());

        for(int i=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=m; j++)
                map[i][j] = str[j-1];
        }

        BFS();
        System.out.println(max);
    }
}