백준 2589, 보물섬(java)

문제 설명

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

2589번: 보물섬

문제가 길다. 아무튼 간단하게 말하자면 하나의 땅에서 다른 땅으로 가는 최대 거리를 구하는 문제이다. 처음 보고는 플로이드 외샬 알고리즘이 생각났으나, 이를 위해서는 따로 그래프를 만들어 줘야 하니 일단 너비 우선 탐색으로 풀어줬다.

문제 풀이

모든 L에서부터 시작해서 갈 수 있는 L까지 너비 우선탐색을 해준 다음에 최대 거리를 찾아주면 된다. 사실 전통적인 너비 우선 탐색 문제 풀이에서 크게 벗어나지 않는 문제였다.

 

일단 반복문을 돌면서 땅이 나오면 해당 땅을 중심으로 너비 우선탐색을 진행한다. 이때 땅으로만 갈 수 있고 한 땅으로 가면 거기까지 간 거리가 최댓값인지 확인해준다. 그리고 너비 우선 탐색으로 구한 최댓값과 정답을 비교해서 더 큰 값을 넣어준다.

 

내가 굉장히 짧게 설명했지만, 사실 너비 우선 탐색을 어느 정도 풀었다면 충분히 이해할 수 있을 거라고 생각한다. 조금 어렵더라도 코드를 보면 무슨 말인이 알 것이다. 

 

아, 그리고 나는 처음에 예전에 초기 값으로 방문해줬던 위치는 다시 방문할 필요가 없다고 생각했다. 왜냐하면 어차피 미리 거기까지는 미리 구한 값인데 굳이 볼 필요가 없다고 생각했기 때문이다. 이는 반은 맞고 반은 틀린 생각이었다. 사실 예전에 시작 노드로 방문했던 노드까지의 값은 이미 구한 상태이다. 하지만, 여기서 중요한 점은 해당 노드를 지나서 다른 노드로 가야 한다는 것이다. 때문에 예전에 시작 노드로 한 번 값을 구해줬다고 방문을 피하지는 말자.

코드

java

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

class Pair {
    int r;
    int c;

    Pair (int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Main {

    public static int rLength, cLength;
    public static char[][] map;
    public static boolean[][] visit;


    public static int[] dR = {-1, 0, 1, 0};
    public static int[] dC = {0, 1, 0, -1};

    public static int bfs(int startR, int startC) {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(startR, startC));
        visit[startR][startC] = true;
        int[][] count = new int[rLength][cLength];
        int max = 0;
        count[startR][startC] = 1;

        while(!queue.isEmpty()) {
            Pair current = queue.poll();
            int cR = current.r;
            int cC = current.c;

            for (int i=0; i<4; i++) {
                int nR = cR + dR[i];
                int nC = cC + dC[i];

                if (nR >= 0 && nR < rLength && nC >= 0 && nC < cLength) {
                    if (count[nR][nC] == 0 && map[nR][nC] == 'L') {
                        count[nR][nC] = count[cR][cC] + 1;
                        queue.add(new Pair(nR, nC));
                        max = Math.max(max, count[nR][nC]);
                    }
                }
            }

        }


        return max;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        rLength = Integer.parseInt(st.nextToken());
        cLength = Integer.parseInt(st.nextToken());

        map = new char[rLength][cLength];
        visit = new boolean[rLength][cLength];

        int answer = 0;

        for (int i=0; i<rLength; i++) {
            char[] c = br.readLine().toCharArray();
            for (int j=0; j<cLength; j++) {
                map[i][j] = c[j];
            }
        }


        for (int i=0; i<rLength; i++) {
            for (int j=0; j<cLength; j++) {
                if (map[i][j] == 'L') {
                    answer = Math.max(answer, bfs(i, j)-1);
                }
            }
        }

        System.out.println(answer);

    }

}