[백준] 2589번 보물섬

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q2589.java

바다와 섬의 정보가 주어진다 섬들 중 최단거리로 이동했을 때, 가장 거리가 먼 2섬이 보물섬이 된다.
이 때 보물섬이 되는 섬들의 거리를 구하여라.

처음 생각

두 섬의 최단거리를 구해야한다. 따라서 BFS를 이용해서 탐색을 진행하였다.

다음 생각

어떤 두 섬이 보물섬이 될지 모르므로 모든 섬에 대해서 거리를 따져주었다.

▶ 입력 받은 배열을 탐색하면서 섬 표시이 L이 보이면 그 L부터 BFS를 시작하여 거리를 판단하고, 그 거리를 계속 최대값과 비교하였다.

▶ 항상 새로운 BFS를 진행하는것이므로 방문 배열도 항상 초기화 시켜주어야한다.

방안

1) Java 풀이

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

package baekjoon.q1000;   import java.io.IOException; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;   public class Q2589 {     static int n,m;     static char[][] arr;     public static void main(String args[]) throws IOException {         Scanner sc = new Scanner(System.in);         n = sc.nextInt();         m = sc.nextInt();         arr = new char[n][m];         for(int i=0;i<n;i++){             String t = sc.next();             for(int j=0;j<m;j++)                 arr[i][j] = t.charAt(j);         }         for(int i=0;i<n;i++){             for(int j=0;j<m;j++){                 if(arr[i][j]=='L') solve(i,j);             }         }         System.out.println(result);     }       static int result;     static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};     private static void solve(int x,int y){         Queue<Pair> queue = new LinkedList<>();         queue.add(new Pair(x,y,0));         boolean[][] visited = new boolean[n][m];         visited[x][y] = true;         while(!queue.isEmpty()){             Pair t = queue.poll();             result = max(result,t.cnt);             for(int i=0;i<4;i++){                 int tx = t.x+dir[i][0];                 int ty = t.y+dir[i][1];                 if(tx<0 || ty<0 || tx>=n || ty>=m) continue;                 if(arr[tx][ty]=='W') continue;                 if(visited[tx][ty]) continue;                 visited[tx][ty]= true;                 queue.add(new Pair(tx,ty,t.cnt+1));             }         }     }       private static int max(int a,int b){return a>b?a:b;}     static class Pair{         int x,y,cnt;         Pair(int x,int y,int cnt){             this.x = x;             this.y = y;             this.cnt = cnt;         }     } }