2589-보물섬

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

2589번: 보물섬

예시

[문제 요약]

• N X M 크기의 보물지도
• 각 칸은 육지(L)나 바다(W)로 표시
• 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻힘
• 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안됨

 

[문제 풀이]

• BFS 알고리즘으로 현재 육지에서 최장거리 육지까지의 최단거리를 구함
• 각칸의 위치별로 최장거리를 구하기 위해 모든 칸을 확인하며,
  육지칸일 경우에 BFS를 돌며 각 위치별 최장거리 계산
• BFS를 진행할때, visit 배열에 방문처리와 함께 위치별 거리를 초기화해서 방문처리가 진행될때 마다 0,1값이 아닌 진행되는 거리를 저장

visited[nx][ny] = visited[curX][curY] + 1;

• 초기화되는 거리를 answer값과 비교하며 최장 거리를 저장

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M, answer;
    static char[][] map;
    static Queue<int[]> queue = new LinkedList<int[]>();
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};

    private static void bfs(int x, int y) {
        int[][] visited = new int[N][M];
        for(int i = 0 ; i< N ; i++) {
            for(int j=0 ; j < M ; j++) {
                visited[i][j] = -1;
            }
        }

        visited[x][y] = 0;
        queue.offer(new int[] {x, y});

        while(! queue.isEmpty()) {
            int[] cur = queue.poll();
            int curX = cur[0];
            int curY = cur[1];

            for(int i = 0 ; i < 4 ; i++) {
                int nx = curX + dx[i];
                int ny = curY + dy[i];

                if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;

                if(map[nx][ny] == 'L' && visited[nx][ny] == -1) {
                    visited[nx][ny] = visited[curX][curY] + 1;
                    queue.offer(new int[] {nx, ny});
                    answer = Math.max(answer, visited[nx][ny]);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        for(int i = 0 ; i < N ; i++) {
            String tmp = br.readLine();
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = tmp.charAt(j);
            }
        }

        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(map[i][j] == 'L') {
                    bfs(i,j);
                }
            }
        }
        System.out.println(answer);
    }
}