<Algorithm> 42. 2589번 보물섬

1. 2589번 보물섬

• 기본 BFS 문제, 최단가리는 BFS를 이용하여 접근하는 편이 좋다.

• 모든 육지에 대해 하나하나 BFS로 탐색하여 가장 큰 값을 출력한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class Main {          static boolean[][] visited;     static int[][] dist;     static int max = 0;     public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br =new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         int N = Integer.parseInt(st.nextToken());         int M = Integer.parseInt(st.nextToken());         int[][] arr = new int[N][M];                  for(int i = 0; i < N; i ++) {             String temp = br.readLine();             for(int j = 0; j < M; j++) {                 if(temp.charAt(j) == 'W') {                     arr[i][j] = 1;                 }else {                     arr[i][j] = 0;                 }             }         }                  Queue<Coordinate> queue;                  for(int i = 0; i < N; i ++) {             for(int j = 0; j < M; j++) {              if(arr[i][j] == 0) {                 visited = new boolean[N][M];                 dist = new int[N][M];                                  dist[i][j] = 0;                 queue = new LinkedList<>();                 queue.add(new Coordinate(i, j));                                  bfs(queue, arr, M, N);              }             }         }         System.out.println(max);     }          public static void bfs(Queue<Coordinate> queue,int[][] arr,int M, int N) {                  int dx[] = {0,0,1,-1};         int dy[] = {1,-1,0,0};                  while(!queue.isEmpty()) {                          Coordinate loc = queue.remove();             int x = loc.x;             int y = loc.y;                          if(dist[x][y] > max){                 max = dist[x][y];             }                          for(int i = 0; i < 4 ; i ++) {                 int nx = x + dx[i];                 int ny = y + dy[i];                                  if(nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && arr[nx][ny] == 0 ) {                     visited[nx][ny] = true;                     queue.add(new Coordinate(nx, ny));                     dist[nx][ny] = dist[x][y] + 1;                                      }                              }          }     } } class Coordinate{     int x,y;       public Coordinate(int x, int y) {         super();         this.x = x;         this.y = y;     } } Colored by Color Scripter

cs