[백준] 2589번 : 보물섬

문제

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다.

보물섬 지도는 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다.

이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다.

보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다.

육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다.

이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다.

보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

문제해결방법

각각의 육지에서 BFS를 돌려서 최장거리를 구한다.

POINT

Visited 배열을 따로 두지 않고 처음 시작하는 L칸에 넣어둔 숫자를 이용해서 체크

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main2589_보물섬 {
 
    public static int X, Y;
    public static int[][] map;
    public static int[][] dir = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    
    public static int BFS(int x, int y) {
        int maxDistance = -1;
        int notVisited = map[x][y];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {x, y});
        map[x][y]++;
        while(!q.isEmpty()) {
            int size = q.size();
            for(int i=0; i<size; i++) {
                int xx = q.peek()[0];
                int yy = q.poll()[1];
                for(int j=0; j<dir.length; j++) {
                    int xxx = xx+dir[j][0];
                    int yyy = yy+dir[j][1];
                    if(xxx>=0&&xxx<X&&yyy>=0&&yyy<Y&&map[xxx][yyy]==notVisited) {
                        map[xxx][yyy]++;
                        q.add(new int[] {xxx, yyy});
                    }
                }
            }
            maxDistance++;
        }
        return maxDistance;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());
        map = new int[X][Y];
        for(int i=0; i<X; i++) {
            String s = br.readLine();
            for(int j=0; j<Y; j++) {
                if(s.charAt(j)=='W') map[i][j] = 0;
                else map[i][j] = 1;
            }
        }
        int max = 0;
        for(int i=0; i<X; i++) {
            for(int j=0; j<Y; j++) {
                if(map[i][j]!=0) {
                    int temp = BFS(i, j);
                    if(max < temp) max = temp;
                }
            }
        }
        System.out.println(max);
    }
}
 

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.